home *** CD-ROM | disk | FTP | other *** search
/ Language/OS - Multiplatform Resource Library / LANGUAGE OS.iso / cocktail / docme.lha / doc.me / minilax.me < prev    next >
Text File  |  1992-09-25  |  100KB  |  3,254 lines
  1. .\" use: pic | tbl | eqn | ditroff -me
  2. .\"
  3. .\"    "@(#)bibmac.me    2.2    9/9/83";
  4. .de IP
  5. .ip \\$1 \\$2
  6. ..
  7. .de LP
  8. .lp
  9. ..
  10. .\"    @(#)bmac.std    2.2    9/9/83;
  11. .\" standard format troff commands
  12. .\" citation formatting strings
  13. .ds [[ [
  14. .ds ]] ]
  15. .ds ], ,\|
  16. .ds ]- -
  17. .ds [. " \&
  18. .ds .] .
  19. .ds [, " \&
  20. .ds ,] ,
  21. .ds [? " \&
  22. .ds ?] ?
  23. .ds [: " \&
  24. .ds :] :
  25. .ds [; " \&
  26. .ds ;] ;
  27. .ds [! " \&
  28. .ds !] !
  29. .ds [" " \&
  30. .ds "] \&"
  31. .ds [' " \&
  32. .ds '] '
  33. .ds [< " \&
  34. .ds >]
  35. .\" reference formmating strings
  36. .ds a] " \&
  37. .ds b] , \&
  38. .ds c] , \&
  39. .ds n] "\& and \&
  40. .ds m] "\& and \&
  41. .ds p] .
  42. .\" reference formmating macros
  43. .de s[   \" start reference
  44. .nh
  45. .IP [\\*([F] 5m
  46. ..
  47. .de e[   \" end reference
  48. .[-
  49. ..
  50. .de []   \" start to display collected references
  51. .LP
  52. ..
  53. .de ][   \" choose format
  54. .ie !"\\*([J"" \{\
  55. .    ie !"\\*([V"" .nr t[ 1    \" journal
  56. .    el            .nr t[ 5    \" conference paper
  57. .\}
  58. .el .ie !"\\*([B"" .nr t[ 3    \" article in book
  59. .el .ie !"\\*([R"" .nr t[ 4    \" technical report
  60. .el .ie !"\\*([I"" .nr t[ 2    \" book
  61. .el                .nr t[ 0    \" other
  62. .\\n(t[[
  63. ..
  64. .de 0[   \" other
  65. .s[
  66. .if !"\\*([A"" \\*([A\\c
  67. .if !"\\*([T"" , \\*([T\\c
  68. .if !"\\*([V"" , Vol. \\*([V\\c
  69. .if !"\\*([O"" , \\*([O\\c
  70. .if !"\\*([D"" , \\*([D\\c
  71. \&.
  72. .e[
  73. ..
  74. .de 1[ \" journal article
  75. .s[
  76. .if !"\\*([A"" \\*([A,
  77. .if !"\\*([T""  \\*([T,
  78. \\fI\\*([J \\*([V\\fP\c
  79. .if !"\\*([N"" ,\\*([N
  80. .if !"\\*([D"" (\\*([D)\c
  81. .if !"\\*([P"" , \\*([P\c
  82. .if !"\\*([I"" , \\*([I\c
  83. \\&.
  84. .if !"\\*([O"" \\*([O.
  85. .e[
  86. ..
  87. .de 2[ \" book
  88. .s[
  89. .ie !"\\*([A"" \\*([A,
  90. .el .if !"\\*([E"" \{\
  91. .       ie \\n([E-1 \\*([E, eds.,
  92. .       el \\*([E, ed.,\}
  93. .if !"\\*([T"" \\fI\\*([T\\fP,
  94. .rm a[
  95. .if !"\\*([I"" .ds a[ \\*([I
  96. .if !"\\*([C"" \{\
  97. .       if !"\\*(a["" .as a[ , \\&
  98. .       as a[ \\*([C\}
  99. .if !"\\*([D"" \{\
  100. .       if !"\\*(a["" .as a[ , \\&
  101. .       as a[ \\*([D\}
  102. \\*(a[.
  103. .if !"\\*([G"" Gov. ordering no. \\*([G.
  104. .if !"\\*([O"" \\*([O.
  105. .e[
  106. ..
  107. .de 3[ \" article in book
  108. .s[
  109. .if !"\\*([A"" \\*([A,
  110. .if !"\\*([T"" \\*([T,
  111. in \\fI\\*([B\\fP\c
  112. .if !"\\*([V"" , vol. \\*([V
  113. .if !~\\*([E~~ \{\
  114. .       ie , \\n([E-1  \\*([E (editors)\c
  115. .       el , \\*([E (editor)\c\}
  116. .if !"\\*([I"" , \\*([I\c
  117. .if !"\\*([C"" , \\*([C\c
  118. .if !"\\*([D"" , \\*([D\c
  119. .if !"\\*([P"" , \\*([P\c
  120. \\&.
  121. .if !"\\*([O"" \\*([O.
  122. .e[
  123. ..
  124. .de 4[ \" report
  125. .s[
  126. .if !"\\*([A"" \\*([A,
  127. .if !~\\*([E~~ \{\
  128. .       ie \\n([E-1 \\*([E, editors.
  129. .       el \\*([E, editor.\}
  130. \\*([T,
  131. \\*([R\c
  132. .if !"\\*([G"" \& (\\*([G)\c
  133. .if !"\\*([I"" , \\*([I\c
  134. .if !"\\*([C"" , \\*([C\c
  135. .if !"\\*([D"" , \\*([D\c
  136. \\&.
  137. .if !"\\*([O"" \\*([O.
  138. .e[
  139. ..
  140. .de 5[ \" conference paper
  141. .s[
  142. .if !"\\*([A"" \\*([A,
  143. .if !"\\*([T"" \\*([T,
  144. \\fI\\*([J\\fP,
  145. .if !"\\*([C"" \\*([C,
  146. .if !"\\*([D"" \\*([D\c
  147. .if !"\\*([P"" , \\*([P\c
  148. \\&.
  149. .if !"\\*([O"" \\*([O.
  150. .e[
  151. ..
  152. .de [-   \" clean up after yourself
  153. .rm [A [B [C [D
  154. .rm [E [F [G
  155. .rm [I [J [K
  156. .rm [N [O [P
  157. .rm [R [T
  158. .rm [V [W
  159. ..
  160. .\"    @(#)bmac.std    2.2    8/24/83;
  161. .\" standard format troff commands
  162. .\" citation formatting strings
  163. .ds [[ [
  164. .ds ]] ]
  165. .ds ], ,\|
  166. .ds ]- -
  167. .ds [. " \&
  168. .ds .] .
  169. .ds [, " \&
  170. .ds ,] ,
  171. .ds [< " \&
  172. .ds >]
  173. .\" reference formmating strings
  174. .ds c] , \&
  175. .ds n] "" and \&
  176. .ds m] "" and \&
  177. .ds a] " \&
  178. .\" reference formmating macros
  179. .de s[   \" start reference
  180. .nh
  181. .IP [\\*([F] 5m
  182. ..
  183. .de e[   \" end reference
  184. .[-
  185. ..
  186. .de []   \" start to display collected references
  187. .SH
  188. References
  189. .LP
  190. ..
  191. .de ][   \" choose format
  192. .ie !"\\*([J"" \{\
  193. .    ie !"\\*([V"" .nr t[ 1    \" journal
  194. .    el            .nr t[ 5    \" conference paper
  195. .\}
  196. .el .ie !"\\*([B"" .nr t[ 3    \" article in book
  197. .el .ie !"\\*([R"" .nr t[ 4    \" technical report
  198. .el .ie !"\\*([I"" .nr t[ 2    \" book
  199. .el                .nr t[ 0    \" other
  200. .\\n(t[[
  201. ..
  202. .de 0[   \" other
  203. .s[
  204. .if !"\\*([A"" \\*([A,
  205. .if !"\\*([T"" \\*([T,
  206. .if !"\\*([O"" \\*([O\c
  207. .if !"\\*([D"" , \\*([D\c
  208. \&.
  209. .e[
  210. ..
  211. .de 1[ \" journal article
  212. .s[
  213. .if !"\\*([A"" \\*([A,
  214. .if !"\\*([T"" \\*([T,
  215. \\fI\\*([J \\*([V\\fP,
  216. .if !"\\*([N"" \\*([N
  217. .if !"\\*([D"" (\\*([D),
  218. .if !"\\*([P"" \\*([P\c
  219. .if !"\\*([I"" , \\*([I\c
  220. \\&.
  221. .if !"\\*([O"" \\*([O.
  222. .e[
  223. ..
  224. .de 2[ \" book
  225. .s[
  226. .ie !"\\*([A"" \\*([A,
  227. .el .if !"\\*([E"" \{\
  228. .       ie \\n([E-1 \\*([E, eds.,
  229. .       el \\*([E, ed.,\}
  230. .if !"\\*([T"" \\fI\\*([T\\fP,
  231. .rm a[
  232. .if !"\\*([I"" .ds a[ \\*([I
  233. .if !"\\*([C"" \{\
  234. .       if !"\\*(a["" .as a[ , \\&
  235. .       as a[ \\*([C\}
  236. .if !"\\*([D"" \{\
  237. .       if !"\\*(a["" .as a[ , \\&
  238. .       as a[ \\*([D\}
  239. \\*(a[.
  240. .if !"\\*([G"" Gov. ordering no. \\*([G.
  241. .if !"\\*([O"" \\*([O.
  242. .e[
  243. ..
  244. .de 3[ \" article in book
  245. .s[
  246. .if !"\\*([A"" \\*([A,
  247. .if !"\\*([T"" \\*([T,
  248. in \\fI\\*([B\\fP,
  249. .if !"\\*([V"" vol. \\*([V,
  250. .if !"\\*([E"" \\*([E (ed.),
  251. .if !"\\*([I"" \\*([I,
  252. .if !"\\*([C"" \\*([C,
  253. .if !"\\*([D"" \\*([D\c
  254. .if !"\\*([P"" , \\*([P\c
  255. \\&.
  256. .if !"\\*([O"" \\*([O.
  257. .e[
  258. ..
  259. .de 4[ \" report
  260. .s[
  261. .if !"\\*([A"" \\*([A,
  262. \\*([T,
  263. \\*([R\c
  264. .if !"\\*([G"" \& (\\*([G)\c
  265. .if !"\\*([I"" , \\*([I\c
  266. .if !"\\*([C"" , \\*([C\c
  267. .if !"\\*([D"" , \\*([D\c
  268. \\&.
  269. .if !"\\*([O"" , \\*([O.
  270. .e[
  271. ..
  272. .de 5[ \" conference paper
  273. .s[
  274. .if !"\\*([A"" \\*([A,
  275. .if !"\\*([T"" \\*([T,
  276. \\fI\\*([J\\fP,
  277. .if !"\\*([C"" \\*([C\c
  278. .if !"\\*([D"" , \\*([D\c
  279. .if !"\\*([P"" , \\*([P\c
  280. \\&.
  281. .if !"\\*([O"" , \\*([O.
  282. .e[
  283. ..
  284. .de [-   \" clean up after yourself
  285. .rm [A [B [C [D
  286. .rm [E [F [G
  287. .rm [I [J [K
  288. .rm [N [O [P
  289. .rm [R [T
  290. .rm [V [W
  291. ..
  292. . so head
  293. .hc ~
  294. .ds ], , 
  295. .EQ
  296. delim off
  297. .EN
  298. .b " "
  299. .sp 1c
  300. .ta 9c
  301. .ft R
  302. .sz 12
  303. \l'17.1c'
  304. .nf
  305.  
  306.  
  307.     Specification of a
  308.     MiniLAX-Interpreter
  309.  
  310.  
  311.     J. Grosch
  312.  
  313. \l'17.1c'
  314. .sp 12.5c
  315. \l'17.1c'
  316. .ft H
  317. .nf
  318.     GESELLSCHAFT F\*UR MATHEMATIK
  319.     UND DATENVERARBEITUNG MBH
  320.  
  321.     FORSCHUNGSSTELLE F\*UR
  322.     PROGRAMMSTRUKTUREN
  323.     AN DER UNIVERSIT\*AT KARLSRUHE
  324. .r
  325. \l'17.1c'
  326. .bp
  327. .oh '''%'
  328. .eh '''%'
  329. .ce 99
  330. .sz 20
  331. .b " "
  332. .sp 2
  333. Project
  334. .sp
  335. .b "Compiler Generation"
  336. .sp
  337. .sz 12
  338. \l'15c'
  339. .sp
  340. .sz 16
  341. .b "Specification of a MiniLAX-Interpreter"
  342. .sp 2
  343. Josef Grosch
  344. .sp 2
  345. .sz 14
  346. Nov. 22, 1991
  347. .sp
  348. .sz 12
  349. \l'15c'
  350. .sp 2
  351. Report No. 22
  352. .sp 2
  353. Copyright \(co 1991 GMD
  354. .sp 2
  355. Gesellschaft f\*ur Mathematik und Datenverarbeitung mbH
  356. Forschungsstelle an der Universit\*at Karlsruhe
  357. Vincenz-Prie\*snitz-Str. 1
  358. D-7500 Karlsruhe
  359. .ce 0
  360. .fi
  361. .bp 1
  362. .ce 99
  363. .b "Specification of a MiniLAX-Interpreter"
  364. .sp
  365. J. Grosch
  366. GMD Forschungsstelle an der Universit\*at Karlsruhe
  367. Vincenz-Prie\*snitz-Str. 1, D-7500 Karlsruhe, Germany
  368. Tel: +721-6622-26
  369. E-Mail: grosch@karlsruhe.gmd.de
  370. .ce 0
  371. .sp
  372. .sh 1 Introduction
  373. .pp
  374. This paper describes the specification of a MiniLAX interpreter using the
  375. following tools from the GMD Toolbox for Compiler Construction
  376. \*([[GrE90\*(]]: The scanner generator
  377. .i rex
  378. \*([[Gro87b\*(]],
  379. the parser generator
  380. .i lalr
  381. \*([[GrV88\*(]],
  382. the generator for abstract syntax trees
  383. .i ast
  384. \*([[Gro91a\*(]],
  385. the attribute evaluator generator
  386. .i ag
  387. \*([[Gro89\*(]],
  388. and the generator for the transformation of attributed trees
  389. .i puma
  390. \*([[Gro91b\*(]].
  391. The target language is Modula-2. The compiler parts which are not
  392. generated by the tools are either taken from a library of reusable
  393. modules\*([<\*([[Gro87a\*(]]\*(>] or are provided as hand-written Modula-2 code.
  394. .pp
  395. The rest of this report is organized as follows:
  396. Section 2 defines the source language MiniLAX.
  397. Section 3 defines the intermediate language ICode which is the input of the interpreter.
  398. Section 4 explains the structure of the generated compiler.
  399. Section 5 contains the specifications for the compiler.
  400. .sh 1 MiniLAX
  401. .pp
  402. The programming language MiniLAX (Mini LAnguage eXample) is a Pascal
  403. relative.
  404. To be more specific it is a subset of the example language LAX\*([,\*([[WaG84\*(]]\*(,]
  405. which is used to illustrate problems in compiler construction.
  406. MiniLAX contains a carefully selected set of language concepts:
  407. .ip \(bu
  408. types
  409. .ip \(bu
  410. type coercion
  411. .ip \(bu
  412. overloaded operators
  413. .ip \(bu
  414. arrays
  415. .ip \(bu
  416. procedures
  417. .ip \(bu
  418. reference and value parameters
  419. .ip \(bu
  420. nested scopes
  421. .pp
  422. Concepts with a low didactical value and concepts
  423. that would make the language unnecessary complex have been
  424. left out, along with
  425. .q "syntactic sugar" .
  426. .sh 2 "Summary of the Language"
  427. .pp
  428. A computer program consists of two essential parts, a
  429. description of
  430. .i "actions"
  431. which are to be performed, and a description of the 
  432. .i "data" ,
  433. which are manipulated by these actions.
  434. Actions are described by
  435. .i "statements" ,
  436. and data are described by
  437. .i "declarations" .
  438. .pp
  439. The data are represented by constants and values of
  440. .i "variables" .
  441. Every variable occurring in a statement must be introduced
  442. by a
  443. .i "variable declaration"
  444. which associates an identifier and a data type with that variable.
  445. The
  446. .i "data type"
  447. essentially defines the set of values which may be assumed by that variable.
  448. The data type is directly described in the variable
  449. declaration.
  450. .pp
  451. There exist three
  452. .i "basic types" :
  453. \fCBoolean\fP, \fCinteger\fP, and \fCreal\fP.
  454. The values of the type Boolean are denoted by reserved
  455. identifiers, the numeric values are denoted by numbers.
  456. .pp
  457. .i "Array types"
  458. are defined by describing the types of their components and an integer range.
  459. A component of an array value is selected by an integer
  460. .i "index" .
  461. The type of the component is the component type of the
  462. corresponding array type.
  463. .pp
  464. The most fundamental statement is the
  465. .i "assignment statement" .
  466. It specifies that a newly computed value be assigned to a
  467. variable (or a component of a variable).
  468. The value is obtained by evaluating an
  469. .i "expression" .
  470. Expressions consist of variables, constants and operators
  471. operating on the denoted quantities and producing new
  472. values.
  473. MiniLAX defines a fixed set of operators, each of which can be
  474. regarded as describing a mapping from the operand types into
  475. the result type.
  476. The set of operators is subdivided into
  477. .(b
  478. Arithmetic operators: addition and multiplication
  479. Boolean operators: negation
  480. Relational operators: comparison
  481. .)b
  482. The result of a comparison is of type \fCBoolean\fP.
  483. The
  484. .i "procedure statement"
  485. causes the execution of the designated procedure (see below).
  486. Assignment and procedure statements are the components or building blocks of
  487. .i "structured statements" ,
  488. which specify sequential, selective, or repeated execution of their components.
  489. Sequential execution of statements is specified by
  490. .i "statement sequences" ,
  491. selective execution by the
  492. .i "if statement" ,
  493. and repeated execution by the
  494. .i "while statement" .
  495. The if statement serves to make the execution of two
  496. alternative statements dependent on the value of a Boolean
  497. expression.
  498. The while statement serves to execute a statement while a
  499. Boolean expression is true.
  500. .pp
  501. A statement sequence can be given a name (identifier), and be
  502. referenced through that identifier.
  503. The statement sequence is then called a
  504. .i "procedure" ,
  505. and its declaration a
  506. .i "procedure declaration" .
  507. Such a declaration may additionally contain a set of
  508. variable declarations and further procedure declarations.
  509. The variables and procedures thus declared can be referenced
  510. only within the procedure itself, and are therefore called
  511. .i "local"
  512. to the procedure.
  513. Their identifiers have significance only within the program
  514. text which constitutes the procedure declaration and which
  515. is called the
  516. .i "scope"
  517. of these identifiers.
  518. Since procedures may be declared local to other procedures,
  519. scopes may be nested.
  520. Entities which are declared in the main program, i.e. not
  521. local to some procedure, are called
  522. .i "global" .
  523. A procedure has a fixed number of parameters, each of which
  524. is denoted within the procedure by an identifier called the
  525. .i "formal parameter" .
  526. Upon an activation of the procedure statement, an actual
  527. quantity has to be indicated for each parameter which can be
  528. referenced from within the procedure through the formal
  529. parameter.
  530. This quantity is called the
  531. .i "actual parameter" .
  532. There are two kinds of parameters: value parameters and
  533. variable parameters.
  534. In the first case, the actual parameter is an expression
  535. which is evaluated once.
  536. The formal parameter represents a local variable to which
  537. the result of this evaluation is assigned before the
  538. execution of the procedure.
  539. In the case of a variable parameter, the actual parameter is
  540. a variable and the formal parameter stands for this
  541. variable.
  542. Possible indices are evaluated before execution of the
  543. procedure.
  544. .sh 2 "Notation, Terminology, and Vocabulary"
  545. .pp
  546. The syntax is described in extended Backus-Naur form.
  547. Syntactic constructs are denoted by (abbreviated) English
  548. words consisting of upper and lower case letters, and
  549. containing at least one lower-case letter.
  550. The angular brackets < and > are omitted.
  551. Strings of letters consisting solely of upper-case letters
  552. stand for themselves, i.e. for reserved identifiers of the
  553. language.
  554. Strings of characters enclosed in single quotes '\ ' are also
  555. to be taken literally.
  556. Square brackets [\ ] denote optional constructs.
  557. Curly brackets {\ } stand for zero or more repetitions of
  558. the enclosed construct.
  559. Alternative constructs are separated by a vertical bar |.
  560. Parentheses (\ ) are used for grouping.
  561. .pp
  562. The basic vocabulary of MiniLAX consists of basic symbols
  563. classified into delimiters, identifiers and constants.
  564. .pp
  565. Spaces, line ends, and comments may occur anywhere in a
  566. program except within a basic symbol.
  567. At least one space, line end or comment must occur between
  568. any two adjacent identifiers or constants.
  569. Otherwise, spaces, line ends, and comments do not influence
  570. the meaning of a program.
  571. .pp
  572. A
  573. .i "comment"
  574. has the form
  575. .TS
  576. center;
  577. l.
  578. \fC'(*'\fP any sequence of characters not containing \(lq*)\(rq \fC'*)'\fP
  579. .TE
  580. .sh 3 "Delimiters"
  581. Delimiters are reserved identifiers or (strings of) special
  582. characters.
  583. .TS
  584. center;
  585. l l.
  586. \fIDelim\fP    ::= \fC':'\fP | \fC';'\fP | \fC':='\fP | \fC'('\fP | \fC')'\fP | \fC'.'\fP | \fC','\fP 
  587.     |\fC'..'\fP | \fC'['\fP | \fC']'\fP | \fC'+'\fP | \fC'*'\fP | \fC'<'\fP
  588.     |\fC'ARRAY'\fP | \fC'BEGIN'\fP | \fC'BOOLEAN'\fP | \fC'DECLARE'\fP | \fC'DO'\fP
  589.     |\fC'ELSE'\fP | \fC'END'\fP | \fC'FALSE'\fP | \fC'IF'\fP | \fC'INTEGER'\fP | \fC'NOT'\fP
  590.     |\fC'OF'\fP | \fC'PROCEDURE'\fP | \fC'PROGRAM'\fP | \fC'READ'\fP | \fC'REAL'\fP
  591.     |\fC'THEN'\fP | \fC'TRUE'\fP | \fC'VAR'\fP | \fC'WHILE'\fP | \fC'WRITE'\fP
  592. .TE
  593. .sh 3 "Identifiers"
  594. Identifiers serve to denote variables and procedures.
  595. Their association must be unique within their scope of
  596. validity, i.e. within the procedure or function in which
  597. they are declared.
  598. .TS
  599. center;
  600. l l.
  601. \fIId\fP    ::= \fILetter\fP { \fILetter\fP | \fIDigit\fP } 
  602. .TE
  603. All letters and digits of an identifier are significant.
  604. Upper and lower case letters are distinguished.
  605. Delimiters are reserved identifiers that can not be used
  606. otherwise.
  607. .sh 3 "Numbers"
  608. The usual decimal notation is used for numbers, which are
  609. the constants of the data types \fCinteger\fP and \fCreal\fP.
  610. The letter 'E' preceding the scale factor is pronounced
  611. as
  612. .q 'times 10 to the power of' .
  613. .TS
  614. center;
  615. l l.
  616. \fIIntConst\fP    ::= \fIDigit\fP { \fIDigit\fP } 
  617. \fIRealConst\fP    ::= [ \fIIntConst\fP ] \fC'.'\fP \fIIntConst\fP [ \fIScaleFactor\fP ] 
  618. \fIScaleFactor\fP    ::= \fC'E'\fP [ \fC'+'\fP | \fC'-'\fP ] \fIIntConst\fP 
  619. .TE
  620. Examples:
  621. .sz -2
  622. .(b
  623. .TS
  624. l l l l.
  625. \fC1    100    .1    87.35E-8\fP
  626. .TE
  627. .)b
  628. .sz +2
  629. .sh 2 "Data Types"
  630. .pp
  631. A data type determines the set of values which variables of
  632. that type may assume.
  633. .TS
  634. center;
  635. l l.
  636. \fIType\fP    ::= \fISimpleType\fP | \fIArrayType\fP 
  637. .TE
  638. .sh 3 "Simple Types"
  639. .TS
  640. center;
  641. l l.
  642. \fISimpleType\fP    ::= \fC'INTEGER'\fP | \fC'REAL'\fP | \fC'BOOLEAN'\fP 
  643. .TE
  644. The values of type INTEGER are a subset of the whole numbers
  645. defined by individual implementations.
  646. Its values are the integers.
  647. .pp
  648. The values of type REAL are a subset of the real numbers
  649. depending on a particular implementation.
  650. The values are denoted by real numbers.
  651. .pp
  652. The values of type BOOLEAN are the truth values denoted by
  653. the reserved identifiers TRUE and FALSE.
  654. .sh 3 "Array Types"
  655. An array type is a structure consisting of a fixed number of
  656. components which are all of the same type, called the
  657. .i "component type" .
  658. The elements of the array are designated by integer
  659. .i "indices" .
  660. The array type specifies the component type as well as a
  661. subrange of the integers to be used as indices.
  662. .TS
  663. center;
  664. l l.
  665. \fIArrayType\fP    ::= \fC'ARRAY'\fP \fC'['\fP \fIIntConst\fP \fC'..'\fP \fIIntConst\fP \fC']'\fP \fC'OF'\fP \fIType\fP 
  666. .TE
  667. Examples:
  668. .sz -2
  669. .(b
  670. \fCARRAY [1..100] OF INTEGER\fP
  671. \fCARRAY [4..7] OF ARRAY [2..2] OF BOOLEAN\fP
  672. .)b
  673. .sz +2
  674. The index range must contain at least one element, i.e. the
  675. lower bound of an index range must not exceed the upper
  676. bound.
  677. .sh 2 "Declarations and Denotations of Variables"
  678. .pp
  679. Variable declarations consist of an identifier denoting the
  680. new variable, followed by its type.
  681. .TS
  682. center;
  683. l l.
  684. \fIVarDecl\fP    ::= \fIId\fP \fC':'\fP \fIType\fP 
  685. .TE
  686. Examples:
  687. .sz -2
  688. .(b
  689. \fCi: INTEGER\fP
  690. \fCr: REAL\fP
  691. \fCb: BOOLEAN\fP
  692. \fCa: ARRAY [4..7] OF ARRAY [2..2] OF INTEGER\fP
  693. .)b
  694. .sz +2
  695. Denotations of variables either designate an entire variable
  696. or a component of an array variable.
  697. Variables occurring in examples in subsequent chapters are
  698. assumed to be declared as indicated above.
  699. .TS
  700. center;
  701. l l.
  702. \fIVar\fP    ::= \fIId\fP | \fIVar\fP \fC'['\fP \fIExpr\fP \fC']'\fP 
  703. .TE
  704. Examples:
  705. .sz -2
  706. .(b
  707. .TS
  708. l l.
  709. \fCi    a[4][2]\fP
  710. .TE
  711. .)b
  712. .sz +2
  713. An entire variable is denoted by its identifier.
  714. A component of an array variable is denoted by the variable
  715. followed by an index expression.
  716. The value of the index expression must lie in the range of
  717. the indices of the corresponding array type.
  718. .sh 2 "Expressions"
  719. .pp
  720. Expressions are constructs denoting rules of computation for
  721. obtaining values of variables and generating new values by
  722. the application of operators.
  723. Expressions consist of operators and operands, i.e.
  724. variables and constants.
  725. .pp
  726. The rules of composition specify operator
  727. .i "precedences"
  728. according to four classes of operators.
  729. The operator NOT has the highest precedence, followed by the
  730. multiplying operator '*', the adding operator '+', and
  731. finally, with the lowest precedence, the relational operator
  732. '<'.
  733. Sequences of operators of the same precedence are executed
  734. from left to right.
  735. .TS
  736. center;
  737. l l.
  738. \fIExpr\fP    ::= \fIExpr\fP ( \fC'+'\fP | \fC'*'\fP | \fC'<'\fP ) \fIExpr\fP | \fC'NOT'\fP \fIExpr\fP 
  739.     |\fC'('\fP \fIExpr\fP \fC')'\fP | \fIVar\fP | \fIIntConst\fP | \fIRealConst\fP
  740.     | \fC'TRUE'\fP | \fC'FALSE'\fP 
  741. .TE
  742. Examples:
  743. .sz -2
  744. .ll -2c
  745. .(b
  746. .TS
  747. expand;
  748. l l l l l l.
  749. \fCi    15    TRUE    2*(i+r)    NOT b    NOT (i<1)\fP
  750. .TE
  751. .)b
  752. .ll +2c
  753. .sz +2
  754. The operators are summarized in the following table:
  755. .TS
  756. box center;
  757. c s s s s s
  758. c|c|l|l|l|l.
  759. Table of Operators
  760. .sp
  761. Priority    Operator    left    right    Result    Operation
  762. \^    \^    Operand    Operand    \^    \^
  763. _
  764. 4    \fCNOT\fP        BOOLEAN    BOOLEAN    negation
  765. _
  766. 3    \fC*\fP    INTEGER    INTEGER    INTEGER    integer multiplication
  767.         REAL    REAL    REAL    real multiplication
  768. _
  769. 2    \fC+\fP    INTEGER    INTEGER    INTEGER    integer addition
  770.         REAL    REAL    REAL    real addition
  771. _
  772. 1    \fC<\fP    INTEGER    INTEGER    BOOLEAN    integer comparison
  773.         REAL    REAL    BOOLEAN    real comparison
  774.         BOOLEAN    BOOLEAN    BOOLEAN    boolean comparison
  775. .TE
  776. Note that, for Boolean values, FALSE < TRUE.
  777. .sh 2 "Statements"
  778. .pp
  779. Statements denote algorithmic actions, and are said to be
  780. .i "executable" .
  781. .TS
  782. center;
  783. l l.
  784. \fIStat\fP    ::= \fIAssignStat\fP | \fICondStat\fP | \fILoopStat\fP | \fIProcStat\fP 
  785. .TE
  786. .sh 3 "Statement sequences"
  787. A statement sequence specifies that its component
  788. statements are to be executed in the same sequence as they
  789. are written.
  790. .TS
  791. center;
  792. l l.
  793. \fIStatSeq\fP    ::= \fIStat\fP { \fC';'\fP \fIStat\fP } 
  794. .TE
  795. .sh 3 "Assignment Statements"
  796. The assignment statement serves to replace the current value
  797. of a variable by a new value specified as an expression.
  798. .TS
  799. center;
  800. l l.
  801. \fIAssignStat\fP    ::= \fIVar\fP \fC':='\fP \fIExpr\fP 
  802. .TE
  803. Examples:
  804. .sz -2
  805. .(b
  806. \fCi := i+1\fP
  807. \fCr := r*3.141592\fP
  808. \fCb := i<1\fP
  809. \fCa[4][2] := r\fP
  810. .)b
  811. .sz +2
  812. The variable and the expression must be of identical type,
  813. with the following exception being permitted: The type of
  814. the variable is REAL, and the type of the expression is
  815. INTEGER.
  816. In any case, the variable must be of a simple type.
  817. .sh 3 "Procedure Statements"
  818. A procedure statement serves to execute the procedure
  819. denoted by the procedure identifier.
  820. The procedure statement may contain a list of
  821. .i "actual parameters"
  822. which are substituted in place of their corresponding
  823. .i "formal parameters"
  824. defined in the procedure declaration.
  825. The correspondence is established by the positions of the
  826. parameters in the lists of actual and formal parameters
  827. respectively.
  828. There exist two kinds of parameters: value
  829. parameters and variable parameters.
  830. .pp
  831. In the case of a
  832. .i "value parameter" ,
  833. the actual parameter must be an expression (of which a variable is a simple
  834. case).
  835. The corresponding formal parameter represents a local
  836. variable of the called procedure, and the current value of
  837. the expression is initially assigned to this variable.
  838. Value parameters must have a simple type.
  839. In the case of a
  840. .i "variable parameter" ,
  841. the actual parameter must be a variable of the same type,
  842. and the corresponding formal parameter
  843. represents this actual variable during the entire execution
  844. of the procedure.
  845. If this variable is a component of an array, its index is
  846. evaluated when the procedure is called.
  847. A variable parameter must be used whenever the parameter
  848. represents a result of the procedure.
  849. .TS
  850. center;
  851. l l.
  852. \fIProcStat\fP    ::= \fIId\fP [ \fC'('\fP \fIExpr\fP { \fC','\fP \fIExpr\fP } \fC')'\fP ] 
  853. .TE
  854. Examples:
  855. .sz -2
  856. .(b
  857. .TS
  858. l l.
  859. \fCnext    Transpose(a,m,n)\fP
  860. .TE
  861. .)b
  862. .sz +2
  863. .sh 3 "Conditional Statements"
  864. The if statement specifies that a statement be executed only
  865. if a certain condition (Boolean expression) is true.
  866. If it is false, the statement following the delimiter ELSE
  867. is to be executed.
  868. .TS
  869. center;
  870. l l.
  871. \fICondStat\fP    ::= \fC'IF'\fP \fIExpr\fP \fC'THEN'\fP \fIStatSeq\fP \fC'ELSE'\fP \fIStatSeq\fP \fC'END'\fP 
  872. .TE
  873. Examples:
  874. .sz -2
  875. .(b
  876. \fCIF i < 0 THEN i := 1 ELSE i := 2 END\fP
  877. .)b
  878. .sz +2
  879. The expression between the delimiters \fCIF\fP and \fCTHEN\fP must be of
  880. type Boolean.
  881. .sh 3 "Repetitive Statements"
  882. The while statement specifies that a certain statement is to
  883. be executed repeatedly.
  884. .TS
  885. center;
  886. l l.
  887. \fILoopStat\fP    ::= \fC'WHILE'\fP \fIExpr\fP \fC'DO'\fP \fIStatSeq\fP \fC'END'\fP 
  888. .TE
  889. The expression controlling repetition must be of type
  890. Boolean.
  891. The statement is repeatedly executed as long as the
  892. expression is true.
  893. If it evaluates to false at the beginning, the statement is
  894. not executed at all.
  895. The while statement
  896. .sz -2
  897. .(b
  898. \fCWHILE b DO s END\fP
  899. .)b
  900. .sz +2
  901. is equivalent to
  902. .sz -2
  903. .(b
  904. \fCIF b\fP
  905. \fCTHEN s; WHILE b DO s END\fP
  906. \fCELSE (* nothing *)\fP
  907. \fCEND\fP
  908. .)b
  909. .sz +2
  910. Examples:
  911. .sz -2
  912. .(b
  913. \fCWHILE a [i] < r DO i := i + 1 END\fP
  914.  
  915. \fCWHILE i < n DO\fP
  916. \fC  r := 2 * r;\fP
  917. \fC  i := i + 1\fP
  918. \fCEND\fP
  919. .)b
  920. .sz +2
  921. .sh 3 "Procedure Declarations"
  922. Procedure declarations serve to define parts of programs and
  923. to associate identifiers with them so that they can be
  924. activated by procedure statements.
  925. .TS
  926. center;
  927. l l.
  928. \fIProcDecl\fP    ::= \fIProcHead\fP \fC';'\fP \fIBlock\fP 
  929. \fIBlock\fP    ::= \fC'DECLARE'\fP \fIDecl\fP { \fC';'\fP \fIDecl\fP } \fC'BEGIN'\fP \fIStatSeq\fP \fC'END'\fP 
  930. \fIDecl\fP    ::= \fIVarDecl\fP | \fIProcDecl\fP 
  931. .TE
  932. The
  933. .i "procedure heading"
  934. specifies the identifier naming the procedure and
  935. the formal parameter identifiers (if any).
  936. The parameters are either value or variable parameters.
  937. .TS
  938. center;
  939. l l.
  940. \fIProcHead\fP    ::= \fC'PROCEDURE'\fP \fIId\fP [ \fC'('\fP \fIFormal\fP { \fC';'\fP \fIFormal\fP } \fC')'\fP ] 
  941. \fIFormal\fP    ::= [ \fC'VAR'\fP ] \fIId\fP \fC':'\fP \fIType\fP 
  942. .TE
  943. If a formal starts with the delimiter VAR it specifies a
  944. variable parameter, otherwise a value parameter.
  945. .pp
  946. The statement sequence of the block specifies the algorithmic
  947. actions to be executed upon an activation of the procedure
  948. by a procedure statement.
  949. .pp
  950. All identifiers introduced in the formal parameter part of
  951. the procedure heading and in the declaration part of the
  952. associated block are
  953. .i "local"
  954. to the procedure declaration which is called the
  955. .i "scope"
  956. of these identifiers.
  957. They are not known outside their scope.
  958. In the case of local variables, their values are undefined
  959. at the beginning of the statement part.
  960. .pp
  961. The use of the procedure identifier in a procedure statement
  962. within its declaration implies recursive execution of the
  963. procedure.
  964. .pp
  965. Examples of procedure declarations:
  966. .sz -2
  967. .(b
  968. \fCPROCEDURE ReadPosInteger (VAR i: INTEGER);\fP
  969. \fCDECLARE\fP
  970. \fC  j: INTEGER;\fP
  971. \fCBEGIN\fP
  972. \fC  i := 0;\fP
  973. \fC  WHILE NOT (0 < i) DO READ (i) END\fP
  974. \fCEND\fP
  975. .)b
  976. .(b
  977. \fCPROCEDURE Sort (VAR a: ARRAY [1..10] OF REAL; n: INTEGER);\fP
  978. \fCDECLARE\fP
  979. \fC  i: INTEGER; j: INTEGER; k: INTEGER; h: REAL;\fP
  980. \fCBEGIN\fP
  981. \fC  i := 1;\fP
  982. \fC  WHILE i < n DO   (* a [1], ... , a [i] is sorted *)\fP
  983. \fC    j := i; k := i;\fP
  984. \fC    WHILE j < n DO   (* a [k] = min {a [i], ... , a [j]} *)\fP
  985. \fC      j := j + 1;\fP
  986. \fC      IF a [j] < a [k] THEN k := j ELSE k := k END\fP
  987. \fC    END;\fP
  988. \fC    h := a [i]; a [i] := a [k]; a [k] := h;\fP
  989. \fC    i := i + 1\fP
  990. \fC  END\fP
  991. \fCEND\fP
  992. .)b
  993. .sz +2
  994. .sh 2 "Input and Output"
  995. .pp
  996. Input and output of values of simple types
  997. is achieved by the standard procedures READ and
  998. WRITE.
  999. .pp
  1000. The procedure READ takes one actual parameter which must be
  1001. a variable of a simple type.
  1002. It reads a value of the corresponding type from the standard
  1003. input and assigns it to that variable.
  1004. .pp
  1005. The procedure WRITE takes one actual parameter which must be
  1006. an expression with a simple type.
  1007. It writes the value of that expression onto the standard
  1008. output.
  1009. .pp
  1010. Example:
  1011. .sz -2
  1012. .(b
  1013. \fC(* read integers and write until a nonpositive number is read *)\fP
  1014. \fCREAD (i);\fP
  1015. \fCWHILE 0 < i DO\fP
  1016. \fC  WRITE (i); READ (i)\fP
  1017. \fCEND\fP
  1018. .)b
  1019. .sz +2
  1020. .sh 2 "Programs"
  1021. .pp
  1022. A MiniLAX program has the form of a procedure declaration except
  1023. for its heading.
  1024. .TS
  1025. center;
  1026. l l.
  1027. \fIProgram\fP    ::= \fC'PROGRAM'\fP \fIId\fP \fC';'\fP \fIBlock\fP \fC'.'\fP 
  1028. .TE
  1029. The identifier following the symbol PROGRAM is the program
  1030. name; it has no further significance inside the program.
  1031. .sp
  1032. Example:
  1033. .sz -2
  1034. .(b
  1035. \fCPROGRAM test;\fP
  1036.  
  1037. \fC  (* read, sort and write an array of n numbers            *)\fP
  1038. \fC  (* this program shows the following features:            *)\fP
  1039. \fC  (*   procedure calls from main level, to a local, and to *)\fP
  1040. \fC  (*     a global procedure                                *)\fP
  1041. \fC  (*   access to a global array                            *)\fP
  1042. \fC  (*   access to local, global and intermediate variables  *)\fP
  1043. \fC  (*   recursion                                           *)\fP
  1044. \fC  (*   reading and writing of all types                    *)\fP
  1045. \fC  (*   integer to real conversion                          *)\fP
  1046. .)b
  1047. .(b
  1048. \fCDECLARE\fP
  1049. \fC  test : BOOLEAN;\fP
  1050. \fC  n    : INTEGER;\fP
  1051. \fC  a    : ARRAY [1..100] OF REAL;\fP
  1052. .)b
  1053. .(b
  1054. \fC  PROCEDURE skip; (* do nothing *)\fP
  1055. \fC  DECLARE\fP
  1056. \fC    n: INTEGER\fP
  1057. \fC  BEGIN\fP
  1058. \fC    n := n\fP
  1059. \fC  END;\fP
  1060. .)b
  1061. .(b
  1062. \fC  PROCEDURE read (VAR n: INTEGER; VAR a: ARRAY [1..100] OF REAL);\fP
  1063. \fC  DECLARE\fP
  1064. \fC    i: INTEGER\fP
  1065. \fC  BEGIN\fP
  1066. \fC    WRITE (TRUE); READ (test);\fP
  1067. \fC    WRITE (5); READ (n);\fP
  1068. \fC    i := 1;\fP
  1069. \fC    WHILE i < n DO\fP
  1070. \fC      i := i + 1; WRITE (1.0E-7); READ (a [i])\fP
  1071. \fC    END\fP
  1072. \fC  END;\fP
  1073. .)b
  1074. .(b
  1075. \fC  PROCEDURE write (m: INTEGER); (* write a [m..n] *)\fP
  1076. \fC  DECLARE\fP
  1077. \fC    x: INTEGER\fP
  1078. \fC  BEGIN\fP
  1079. \fC    WRITE (a [m]);\fP
  1080. \fC    IF m < n THEN write (m + 1) ELSE skip END\fP
  1081. \fC  END;\fP
  1082. .)b
  1083. .(b
  1084. \fC  PROCEDURE sort (VAR a: ARRAY [1..100] OF REAL); (* sort a [1..n] *)\fP
  1085. \fC  DECLARE\fP
  1086. \fC    i : INTEGER;\fP
  1087. \fC    j : INTEGER;\fP
  1088. \fC    k : INTEGER;\fP
  1089. \fC    h : REAL;\fP
  1090. \fC    ok: BOOLEAN;\fP
  1091. .)b
  1092. .(b
  1093. \fC    PROCEDURE check (VAR ok: BOOLEAN); (* check order of a [1..n] *)\fP
  1094. \fC    DECLARE\fP
  1095. \fC      continue: BOOLEAN\fP
  1096. \fC    BEGIN\fP
  1097. \fC      IF test THEN write (1) ELSE skip END;\fP
  1098. \fC      i := 1; continue := TRUE;\fP
  1099. \fC      WHILE continue DO\fP
  1100. \fC        IF i < n THEN\fP
  1101. \fC          continue := NOT (a [i + 1] < a [i]);\fP
  1102. \fC          IF continue THEN i := i + 1 ELSE skip END\fP
  1103. \fC        ELSE\fP
  1104. \fC          continue := FALSE\fP
  1105. \fC        END\fP
  1106. \fC      END;\fP
  1107. \fC      ok := NOT (i < n)\fP
  1108. \fC    END\fP
  1109. .)b
  1110. .(b
  1111. \fC  BEGIN (* sort *)\fP
  1112. \fC    i := 1;\fP
  1113. \fC    WHILE i < n DO\fP
  1114. \fC      write (1);\fP
  1115. \fC      j := i; k := i;\fP
  1116. \fC      WHILE j < n DO   (* a [k] = MIN a [i..j] *)\fP
  1117. \fC        j := j + 1;\fP
  1118. \fC        IF a [j] < a [k] THEN k := j ELSE skip END\fP
  1119. \fC      END;\fP
  1120. \fC      h := a [i]; a [i] := a [k]; a [k] := h;\fP
  1121. \fC      i := i + 1\fP
  1122. \fC    END;\fP
  1123. \fC    check (ok); WRITE (ok)\fP
  1124. \fC  END\fP
  1125. .)b
  1126. .(b
  1127. \fCBEGIN (* main program *)\fP
  1128. \fC  a [1] := 2.1415926536;\fP
  1129. \fC  a [1] := a [1] + 1.0;\fP
  1130. \fC  read (n, a);\fP
  1131. \fC  sort (a);\fP
  1132. \fC  IF NOT test THEN write (0) ELSE skip END\fP
  1133. \fCEND.\fP
  1134. .)b
  1135. .sz +2
  1136. .sh 1 ICode
  1137. .pp
  1138. The intermediate code (ICode) for MiniLAX is a subset of the intermediate
  1139. code for Pascal (P-Code)\*([.\*([[NAJ76\*(]]\*(.]
  1140. ICode programs consist of simple instructions
  1141. for a hypothetical computer \(em a stack machine.
  1142. .sh 2 "The ICode Machine"
  1143. .pp
  1144. The ICode Machine consists of three registers and memory.
  1145. The registers are
  1146. .(b
  1147. - PC the program counter
  1148. - SP the stack pointer
  1149. - AP the activation record pointer
  1150. .)b
  1151. .pp
  1152. The program counter points to the current instruction in the memory.
  1153. The stack pointer points to the highest occupied stack cell.
  1154. The activation record pointer points to the 'static link'
  1155. field of the current activation record.
  1156. .pp
  1157. The memory is divided in two parts, one containing the program
  1158. (Code) and the other containing data (Store). Code is an array
  1159. of ICode instructions.
  1160. Store is organized as stack (growing upwards)
  1161. which contains the data of the program executed.
  1162. Each activation of a procedure results in pushing an activation
  1163. record on the stack, which contains storage for parameters and
  1164. local data.
  1165. .pp
  1166. An activation record has the following layout:
  1167. .sp 0.5
  1168. .in +3
  1169. .PS
  1170.     boxwid = 2.8
  1171.     boxht  = 0.7
  1172.     down
  1173. A:    box
  1174. B:    box "- values of value parameters" "- addresses of reference parameters"
  1175.     box ht 0.3 "return address"
  1176. C:    box ht 0.3 "dynamic link"
  1177. D:    box ht 0.3 "static link"
  1178.     right
  1179.     " store for local data" at A.e ljust
  1180.     " store for parameters" at B.e ljust
  1181.     " procedure call" at C.ne ljust
  1182.     " information" at C.se ljust
  1183.     move left from D.w
  1184. E:    arrow to D.w
  1185.     "AP" at E.w rjust
  1186. .PE
  1187. .in -3
  1188. .sp 1
  1189. .pp
  1190. At initialization time, the static and dynamic links and the return address
  1191. of the main program are all set to 0. The registers are initialized as
  1192. follows: PC := 0, SP := 3, and AP := 1.
  1193. The start address is 0, i.e. Code [0] contains
  1194. the first ICode instruction to be executed. PC is incremented before
  1195. the according instruction is executed. The interpreter stops at return
  1196. from the main program. The stop condition is: (PC = 0).
  1197. .pp
  1198. A procedure call enforces
  1199. .ip -
  1200. the creation of static and dynamic links of the new activation
  1201. record (ICode instruction: MST)
  1202. .ip -
  1203. parameter passing: The values of value parameters and the addresses
  1204. of reference parameters are evaluated and pushed on the stack.
  1205. .ip -
  1206. storing the return address and a jump to the procedure (ICode
  1207. instruction: JSR)
  1208. .ip -
  1209. reservation of store for local data of the new activation
  1210. record (ICode instruction: ENT)
  1211. .pp
  1212. A return from a procedure enforces
  1213. .ip -
  1214. discarding the current activation record by updating the registers 
  1215. .sh 2 "ICode Instructions"
  1216. .pp
  1217. For each ICode instruction its operation code, its parameters
  1218. and its meaning is given in the following. The meaning is given
  1219. as text and as formula which describe operations
  1220. on the runtime stack. To simplify the description, within
  1221. formulas it is not taken care about the types of the stack elements.
  1222. .pp
  1223. If not further mentioned, the operations apply to the top
  1224. of the stack, which contains the actual element.
  1225. The following shorthand notations are used:
  1226. .sp
  1227. .nf
  1228. .ta 4
  1229. S    runtime stack
  1230. base(P)    returns a pointer to the P'th static predecessor of the current activation record
  1231. .fi
  1232. .sp
  1233. An instruction may have up to two parameters with the following meaning:
  1234. .nf
  1235. .sp 0.5
  1236. .ta 5
  1237. o    offset
  1238. c, c1, c2    constants
  1239. a    address (index of code section)
  1240. t    indicates type integer (1), real (2) or boolean (3)
  1241. l    block level difference between current and referenced activation record
  1242. .fi
  1243. .sp
  1244. Note: The types integer, real and boolean are encoded with 1, 2, and 3.
  1245. The boolean values FALSE and TRUE are encoded by 0 and 1.
  1246. .sp
  1247. 1. Load instructions:
  1248. .sp 0.5
  1249. .ta 2.5 7 20
  1250. .nf
  1251. LDA    l o    SP:=SP+1;    load address with base and offset
  1252.         S[SP]:=base(l)+o;
  1253. .sp 0.2
  1254. LDC    t c    SP:=SP+1;    load constant c of type t
  1255.         S[SP]:=c;
  1256. .sp 0.2
  1257. LDI        S[SP]:=S[S[SP]];    load indirect
  1258. .fi
  1259. .sp
  1260. 2. Store instructions:
  1261. .sp 0.5
  1262. .nf
  1263. STI        S[S[SP-1]]:=S[SP];    store into address contained
  1264.         SP:=SP-1;    in the element below the top
  1265. .fi
  1266. .sp
  1267. 3. Jump instructions:
  1268. .sp 0.5
  1269. .nf
  1270. JMP    a    PC:=a;    unconditional jump
  1271. .sp 0.2
  1272. FJP    a    if not S[SP] then PC:=a;    conditional jump
  1273.         SP:=SP-1;
  1274. .fi
  1275. 4. Arithmetic instructions:
  1276. .sp 0.5
  1277. .nf
  1278. ADD    t    SP:=SP-1;    addition of type t
  1279.         S[SP]:=S[SP]+S[SP+1];
  1280. .sp 0.2
  1281. SUB        SP:=SP-1;    integer subtraction
  1282.         S[SP]:=S[SP]-S[SP+1];
  1283. .sp 0.2
  1284. MUL    t    SP:=SP-1;    multiplication of type t
  1285.         S[SP]:=S[SP]*S[SP+1];
  1286. .fi
  1287. .sp
  1288. 5. Logic instructions:
  1289. .sp 0.5
  1290. .nf
  1291. INV        S[SP]:=not S[SP];
  1292. .sp 0.2
  1293. LES    t    SP:=SP-1;    less operation of type t
  1294.         S[SP]:=S[SP]<S[SP+1];
  1295. .fi
  1296. .sp
  1297. 6. Address calculation instructions:
  1298. .sp 0.5
  1299. .nf
  1300. IXA    c    SP:=SP-1;    compute indexed address
  1301.         S[SP]:=c*S[SP+1]+S[SP];
  1302. .fi
  1303. .sp
  1304. 7. Convert instructions:
  1305. .sp 0.5
  1306. .nf
  1307. FLT        S[SP]:=real(S[SP]);    converts from integer to real
  1308. .fi
  1309. .sp
  1310. 8. Input-output instructions:
  1311. .sp 0.5
  1312. .nf
  1313. WRI    t    write(S[SP]); SP:=SP-1;
  1314. .sp 0.2
  1315. REA    t    SP:=SP+1; read(S[SP]);
  1316. .fi
  1317. .sp
  1318. 9. Subroutine handling instructions:
  1319. .sp 0.5
  1320. .nf
  1321. MST    l        activation record initialization:
  1322.         S[SP+1]:=base(l);    - store static predecessor
  1323.         S[SP+2]:=AP;    - store dynamic predecessor
  1324.         SP:=SP+3;    return address (=S[SP+3]) is stored by JSR
  1325. .sp 0.2
  1326. JSR    o a    AP:=SP-(o+2);    set AP to point to new activation record
  1327.             o = #locations for parameters
  1328.         S[AP+2]:=PC;    store return address
  1329.         PC:=a    set PC to first instruction of subroutine
  1330. .sp 0.2
  1331. ENT    o    SP:=SP+o    storage reservation for new block
  1332.             o = length of local data segment
  1333. .sp 0.2
  1334. RET        SP:=AP-1;    return from subroutine:
  1335.         PC:=S[SP+3];    - fetch return address to restore PC
  1336.         AP:=S[SP+2];    - restore activation record pointer AP
  1337. .fi
  1338. .sp
  1339. 10. check instructions:
  1340. .sp 0.5
  1341. .nf
  1342. CHK    c1 c2    if (S[SP]<c1) or    check against upper and lower bounds
  1343.            (S[SP]>c2) then error
  1344. .fi
  1345. .if 0 \{\
  1346. .pp
  1347. Table 2 gives an overview of the parts of the specification and
  1348. the generated source modules. The sizes are given in terms of numbers of
  1349. lines. If two numbers are present the first one refers to the definition
  1350. module and the second one to the implementation module.
  1351. The complete specification is reproduced in Appendix B.
  1352. .(z
  1353. .ce
  1354. Table 2: Sizes of Specifications and Modules
  1355. .sp
  1356. .TS
  1357. box center tab (;);
  1358. l | c s | l | c s
  1359. l | r r | l | r r.
  1360. specification file;lines;module;lines
  1361. _
  1362. minilax.rex     ;    ;173;Scanner   ; 48 +;753
  1363.                 ;    ;   ;Source    ; 42 +; 35
  1364. <library>       ;    ;   ;Idents    ; 55 +;169
  1365. <library>       ;    ;   ;StringMem ; 49 +;126
  1366. minilax.lalr    ;    ;189;Parser    ; 48 +;749
  1367.                 ;    ;   ;Errors    ; 35 +;224
  1368. minilax.cg      ;    ;435;Tree      ;201 +;974
  1369.                 ;    ;   ;Semantics ;  9 +;342
  1370. minilax.def     ;    ;129;Definitions;95 +;242
  1371. Types.md/mi     ;53 +;168;Types     ; 53 +;168
  1372. Coercions.md/mi ;28 +; 55;Coercions ; 28 +; 55
  1373. ICode.md/mi     ; 7 +;122;ICode     ;  7 +;122
  1374. ICodeInter.md/mi;22 +;342;ICodeInter; 22 +;342
  1375. minilax.mi      ;    ; 18;minilax   ;     ; 18
  1376. _
  1377.                 ;    ;1741;         ;     ;5011
  1378. .TE
  1379. .)z
  1380. .\}
  1381. .(z
  1382. .sp 0.5
  1383. .PS
  1384. define par #
  1385.     box invis $1
  1386.     line up boxht right boxwid * 1/6 from last box.sw
  1387.     line right boxwid * 5/6
  1388.     line down boxht left boxwid * 1/6
  1389.     line left boxwid * 5/6
  1390. #
  1391. inch    = 2.54
  1392. cm    = 1 / inch
  1393. boxwid    = 2.0 * cm
  1394. boxht    = 1.5 * cm
  1395. dist    = 0.5 * cm
  1396. delta    = boxwid * 1/12
  1397.  
  1398. So:    box "Source"
  1399.     move right dist
  1400. Sc:    par("Scanner")
  1401.     move right dist at Sc.e
  1402. Pa:    par("Parser")
  1403.     move right dist at Pa.e
  1404. Tr:    box "Tree"
  1405.     move right dist
  1406. Ic:    par("ICode")
  1407.     move right dist at Ic.e
  1408. Ii:    box "ICode-" "Inter"
  1409.  
  1410.     move            to Pa.n + (- boxwid/2, 2 * cm)
  1411. Ml:    par("minilax")
  1412. Id:    box "Idents"        at Sc.s + (0, -2 * cm)
  1413. Er:    box "Errors"        at Pa.s + (0, -2 * cm)
  1414.     move            to Ic.s + (boxwid/2, -2 * cm)
  1415. Se:    par("\s-2Semantics\s+2")
  1416.  
  1417. Sm:    box "String-" "Memory"    at Id.s + (0, -2 * cm)
  1418. Ty:    box "Types"        at Se.s + (0, -2 * cm)
  1419. De:    box "Definitions"    at Se.s + (- (dist + boxwid), -2 * cm)
  1420.  
  1421.     arrow from So.e to Sc.w + (delta, 0)
  1422.     arrow from Sc.e - (delta, 0) to Pa.w + (delta, 0)
  1423.     arrow from Pa.e - (delta, 0) to Tr.w
  1424.     arrow from Tr.e to Ic.w + (delta, 0)
  1425.     arrow from Ic.e - (delta, 0) to Ii.w
  1426.  
  1427.     arrow from Sc.s to Id.n <->
  1428.     arrow from Id.s to Sm.n <->
  1429.     arrow from Sc.s to Er.n
  1430.     arrow from Pa.s to Er.n
  1431.     arrow from Se.w + (delta, 0) to Er.e
  1432.     arrow from Tr.s to Se.n <->
  1433.     arrow from Se.s to De.n <->
  1434.     arrow from Se.s to Ty.n <->
  1435.  
  1436.     down
  1437.     box "source" "file" invis at So.n + (0, 2 * cm)
  1438.     arrow to So.n
  1439.     box "input" "data" invis at Ii.n + (0, 2 * cm)
  1440.     arrow to Ii.n
  1441.     up
  1442.     box "listing" invis at Er.s - (0, 2 * cm)
  1443.     arrow to Er.s <-
  1444.     box "output" "data" invis at Ii.s - (0, 2 * cm)
  1445.     arrow to Ii.s <-
  1446.  
  1447. L1:    box at So.s - (0, 7 * cm)
  1448.     move to L1.s - (0, 2.0 * cm)
  1449. L2:    par()
  1450.     "data module (contains data and operations)" ljust at L1.e + (1 * cm, 0)
  1451.     "function module (contains only operations)" ljust at L2.e + (1 * cm, 0)
  1452. .PE
  1453. .sp 2
  1454. .ce
  1455. Fig. 1: Module structure \- data flow (simplified)
  1456. .)z
  1457. .sh 1 "Compiler Structure"
  1458. .pp
  1459. Figure 1 gives an overview of the modules of the compiler.
  1460. .sh 2 Scanning
  1461. .pp
  1462. The scanner module as well as the source module are generated by the
  1463. scanner generator
  1464. .i Rex .
  1465. The source module provides access to the source file.
  1466. The scanner specification in the file
  1467. .i minilax.scan
  1468. contains only six rules describing comments, numbers, and identifiers. Except for comments,
  1469. a rule consists of a regular expression, an attribute computation, and a RETURN statement.
  1470. The rules for the other tokens including the keywords are extracted automatically from the
  1471. context-free grammar of the language and inserted at the line
  1472. .FT
  1473. INSERT RULES
  1474. .FR
  1475. using the preprocessors
  1476. .i "cg -xz"
  1477. and
  1478. .i rpp
  1479. \*([[Gro91c\*(]]. The source position of all tokens is
  1480. passed automatically in the variable
  1481. .i Attribute
  1482. to later compiler phases to be used for error messages.
  1483. .sh 2 Conversion
  1484. .pp
  1485. The three conversion operations used by the scanner are taken from a library
  1486. of reusable modules. The procedures
  1487. .i StringToInt
  1488. and
  1489. .i StringToReal
  1490. map strings to integer and real numbers. The procedure
  1491. .i MakeIdent
  1492. unambiguously maps identifiers (strings) to integer numbers using hashing
  1493. and a string memory.
  1494. .sh 2 Parsing
  1495. .pp
  1496. The parser module as well as the error reporting module are generated using
  1497. the LALR(1) parser generator
  1498. .i Lalr .
  1499. The parser specification in the file
  1500. .i minilax.pars
  1501. contains an LALR(1) grammar for MiniLAX.
  1502. As the subgrammar for expressions is ambiguous operator precedences are
  1503. given in the PREC section to solve this problem. The grammar is written in a
  1504. style that reflects the semantic structure of the language: Almost every
  1505. grammar rule corresponds to one node type in the abstract syntax tree.
  1506. .sh 2 "Tree Construction"
  1507. .pp
  1508. The tree module is generated by the generator for abstract syntax trees
  1509. .i Ast .
  1510. This module implements an abstract data type for trees. It primarily defines
  1511. the structure of the trees and provides procedures to construct the tree
  1512. nodes. The specification for the syntax tree is contained in the file
  1513. .i minilax.cg
  1514. (first page). It constitutes a context-free grammar augmented by several
  1515. features like rule names, selector names, typed attributes, and inheritance
  1516. which are described in detail in\*([<\*([[Gro91a\*(]]\*(>]. Each grammar rule corresponds to a
  1517. node type in the abstract syntax tree. For every node type a constructor procedure is
  1518. provided whose name consists of the rule name with the prefix 'm'.
  1519. .pp
  1520. The specification tries to keep the tree as small as possible.
  1521. The inheritance mechanism allows to avoid all chain rules. There are no
  1522. nodes for sequences of declarations, statements, etc.. Instead, every node
  1523. for a declaration or a statement has a field named
  1524. .i Next
  1525. describing the successor entity. Except for expressions, no separate nodes
  1526. are used for identifiers. The information is included as attribute in node types called
  1527. .i "Proc, Var, Formal" ,
  1528. and
  1529. .i Call .
  1530. The source position is stored only at the nodes where it might be needed
  1531. during semantic analysis. The above measures not only reduce the amount of
  1532. storage but they also reduce run time because less information has to be
  1533. produced and processed.
  1534. .pp
  1535. The mapping of the concrete syntax to the abstract syntax tree is specified
  1536. in the parser specification by the actions associated with the grammar
  1537. rules. The underlying principle is an attribute grammar with only one
  1538. synthesized attribute called
  1539. .i Tree .
  1540. Except for (semantic) chain rules, the action of every grammar rule
  1541. constructs one tree node by calling a generated constructor procedure.
  1542. .pp
  1543. For sequences of declarations, statements, etc. left recursive grammar rules
  1544. are used in order to avoid overflow of the parse stack. (This is historic
  1545. because the latest version of
  1546. .i Lalr
  1547. has a flexible stack which will never overflow.) This leads to syntax trees
  1548. where the elements of sequences are in the wrong order. The calls of the
  1549. procedure
  1550. .i ReverseTree
  1551. which is generated by
  1552. .i Ast
  1553. at certain places solves this problem.
  1554. .sh 2 "Semantic Analysis"
  1555. .pp
  1556. Semantic analysis which consists of name analysis, type checking, and
  1557. computation of code generation attributes is generated using the attribute
  1558. grammar generator
  1559. .i Ag
  1560. \*([[Gro89\*(]].
  1561. It generates evaluators for ordered attribute grammars. The attribute
  1562. computations have to be specified in a functional style. They are written in
  1563. the desired target language. They can use external functions of separately
  1564. compiled abstract data types.
  1565. .i Ag
  1566. cooperates with
  1567. .i Ast
  1568. in the sense that both tools understand the same specification language and
  1569. the generated attribute evaluators operate on the trees generated by
  1570. .i Ast .
  1571. .i Ag
  1572. offers many features which are improvements over traditional attribute
  1573. grammar systems like attributes local to rules, modules, tree-valued
  1574. attributes, and inheritance. Attributes of left-hand side symbols are
  1575. denoted just by the attribute name. For attributes of right-hand side symbols
  1576. the attribute name is preceded by the selector name of the symbol and a
  1577. colon.
  1578. .pp
  1579. The semantic analysis is specified by the attribute grammar in the file
  1580. .i minilax.cg .
  1581. The attribute grammar is based on the abstract syntax. It is divided into
  1582. modules where each module describes the computation of one attribute. The
  1583. context conditions are also contained in a separate module. The first page
  1584. of the specification describes the abstract syntax and the intrinsic
  1585. attributes whose values are supplied by the scanner and parser. The
  1586. attributes for semantic analysis are introduced in the individual modules.
  1587. .sh 2 "Name Analysis"
  1588. .pp
  1589. Name analysis is controlled by the modules
  1590. .i Decls
  1591. and
  1592. .i Env .
  1593. The attributes
  1594. .i DeclsIn
  1595. and
  1596. .i DeclsOut
  1597. collect the declarations in a scope. The attribute
  1598. .i Env
  1599. describes the environment information. It is distributed over all
  1600. declarations and statements where it is valid. Used identifiers are mapped
  1601. to the denoted objects by the procedure
  1602. .i Identify .
  1603. .pp
  1604. The data structure and procedures used in name analysis are provided by the
  1605. external module
  1606. .i Definitions .
  1607. This module is generated by
  1608. .i Ast
  1609. out of the specification in the file
  1610. .i Definitions.cg .
  1611. The last seven lines describe the data structure and the corresponding
  1612. constructor procedures. Some additional operations like e. g.
  1613. .i Identify
  1614. are provided as Modula-2 code.
  1615. .sh 2 "Operator Identification"
  1616. .pp
  1617. Operator identification for MiniLAX is trivial. It is handled in an ad hoc
  1618. manner in the module
  1619. .i TypeCode
  1620. by computing the attribute
  1621. .i TypeCode
  1622. for certain node types.
  1623. .sh 2 "Semantic Checks"
  1624. .pp
  1625. The attribute grammar modules
  1626. .i Formals
  1627. and
  1628. .i Types
  1629. control the type determination for every subexpression. The module
  1630. .i Conditions
  1631. contains all context checks for MiniLAX. The above modules use the
  1632. operations of the external module
  1633. .i Types
  1634. for manipulation of types. This module is conveniently generated by
  1635. .i Puma
  1636. \*([[Gro91b\*(]] out of a specification contained in the file
  1637. .i Types.puma .
  1638. The reporting of error messages is completely
  1639. expressed in the target language. The source position is treated like any
  1640. other attribute. This allows to combine error messages with precise source positions.
  1641. .sh 2 "Action Mapping"
  1642. .pp
  1643. The mapping of the abstract syntax tree to the intermediate language is
  1644. carried out in two steps. First, using the attribute grammar code generation
  1645. attributes are computed. Second, a transformation module generated by
  1646. .i Puma
  1647. \*([[Gro91b\*(]] traverses the attributed tree and emits the code.
  1648. .pp
  1649. The module
  1650. .i Co
  1651. computes for every subexpression an attribute describing the
  1652. coercions to be applied. Coercions are operations which are not explicitly
  1653. given in the source program. The procedure
  1654. .i Coerce
  1655. is imported from the external module
  1656. .i Types .
  1657. The module
  1658. .i DataSize
  1659. computes the offset of all variables.
  1660. The module
  1661. .i CodeSize
  1662. computes the code address of every target code instruction.
  1663. The module
  1664. .i Level
  1665. distributes the nesting level over the complete syntax tree.
  1666. The module
  1667. .i Label
  1668. copies the values of certain code addresses into local attributes. The
  1669. intention is to allow an optimizer to turn the attribute pair
  1670. .i CodeSizeIn/Out
  1671. into a global variable. The information gathered in the modules
  1672. .i "DataSize, CodeSize" ,
  1673. and
  1674. .i Level
  1675. is added to the definition table (see module
  1676. .i Decls )
  1677. in a functional way.
  1678. .pp
  1679. The program module
  1680. .i ICode
  1681. is generated by
  1682. .i Puma
  1683. \*([[Gro91b\*(]] out of the specification in the file
  1684. .i ICode.puma .
  1685. It recursively traverses the attributed tree and emits the intermediate code.
  1686. For this purpose it uses the operations of the hand-written module
  1687. .i ICodeInter
  1688. which stores the intermediate code in an array and provides an interpreter
  1689. and a printing routine for it. The reason for not using the attribute
  1690. grammar for code generation is the following:
  1691. The attribute grammar would compute the code as a list- or tree-valued
  1692. attribute of the root. As attribute grammars have no notion of output an
  1693. external function would have to transform this attribute value into the
  1694. array structure required by the interpreter. We save storage and runtime to
  1695. compute the code attribute by constructing the array directly.
  1696. Specifying the mapping to intermediate code using a separate module
  1697. is competitive to an attribute grammar version in terms of
  1698. clarity and size.
  1699. .pp
  1700. The module
  1701. .i minilax
  1702. is the main program that glues it all together.
  1703. .bp
  1704. .sh 1 "Specification"
  1705. .de FT
  1706. .)l
  1707. .sh 2 "\\$1"
  1708. .(l L
  1709. .ft C
  1710. .sz -4
  1711. ..
  1712. .(l
  1713. .FT "minilax.scan"
  1714. EXPORT  {
  1715. FROM Idents     IMPORT tIdent;
  1716. FROM Positions  IMPORT tPosition;
  1717.  
  1718. INSERT tScanAttribute
  1719. }
  1720.  
  1721. GLOBAL  {
  1722. FROM SYSTEM     IMPORT ADR;
  1723. FROM Strings    IMPORT tString, StringToInt, StringToReal;
  1724. FROM Idents     IMPORT tIdent, NoIdent, MakeIdent;
  1725. FROM Errors     IMPORT Message, MessageI, Error, String;
  1726.  
  1727. INSERT ErrorAttribute
  1728. }
  1729.  
  1730. LOCAL   { VAR Word: tString; }
  1731.  
  1732. DEFAULT {
  1733.    GetWord (Word);
  1734.    MessageI ("illegal character", Error, Attribute.Position, String, ADR (Word));
  1735. }
  1736.  
  1737. EOF     {
  1738.    IF yyStartState = Comment THEN
  1739.       Message ("unclosed comment", Error, Attribute.Position);
  1740.    END;
  1741. }
  1742.  
  1743. DEFINE  digit   = {0-9} .
  1744.         letter  = {a-z A-Z} .
  1745.  
  1746. START   Comment
  1747.  
  1748. RULE
  1749.           "(*"  :- {yyStart (Comment);}
  1750. #Comment# "*)"  :- {yyStart (STD);}
  1751. #Comment# "*" | - {*\\t\\n} + :- {}
  1752.  
  1753. #STD# digit +   : {GetWord (Word);
  1754.                    Attribute.IntegerConst.Integer := StringToInt (Word);
  1755.                    RETURN IntegerConst;}
  1756.  
  1757. #STD# digit * "." digit + (E {+\\-} ? digit +) ?
  1758.                 : {GetWord (Word);
  1759.                    Attribute.RealConst.Real := StringToReal (Word);
  1760.                    RETURN RealConst;}
  1761.  
  1762. INSERT RULES #STD#
  1763.  
  1764. #STD# letter (letter | digit) *
  1765.                 : {GetWord (Word);
  1766.                    Attribute.Ident.Ident := MakeIdent (Word);
  1767.                    RETURN Ident;}
  1768. .FT "minilax.pars"
  1769. PARSER minilax
  1770.  
  1771. PREC    LEFT    '<'                                     /* operator precedence  */
  1772.         LEFT    '+'
  1773.         LEFT    '*'
  1774.         LEFT    NOT
  1775.  
  1776. PROPERTY INPUT
  1777.  
  1778. RULE                                                    /* concrete syntax      */
  1779.  
  1780. Prog            = PROGRAM Ident ';' 'DECLARE' Decls 'BEGIN' Stats 'END' '.' .
  1781. Decls           = <
  1782.    Decls1       = Decl .
  1783.    Decls2       = Decls ';' Decl .
  1784. > .
  1785. Decl            = <
  1786.    Var          = Ident ':' Type .
  1787.    Proc0        = PROCEDURE Ident ';' 'DECLARE' Decls 'BEGIN' Stats 'END' .
  1788.    Proc         = PROCEDURE Ident '(' Formals ')' ';'
  1789.                                       'DECLARE' Decls 'BEGIN' Stats 'END' .
  1790. > .
  1791. Formals         = <
  1792.    Formals1     = Formal .
  1793.    Formals2     = Formals ';' Formal .
  1794. > .
  1795. Formal          = <
  1796.    Value        = Ident ':' Type .
  1797.    Ref          = VAR Ident ':' Type .
  1798. > .
  1799. Type            = <
  1800.    Int          = INTEGER .
  1801.    Real         = REAL .
  1802.    Bool         = BOOLEAN .
  1803.    Array        = ARRAY '[' Lwb: IntegerConst '..' Upb: IntegerConst ']' OF Type .
  1804. > .
  1805. Stats           = <
  1806.    Stats1       = Stat .
  1807.    Stats2       = Stats ';' Stat .
  1808. > .
  1809. Stat            = <
  1810.    Assign       = Adr ':=' Expr .
  1811.    Call0        = Ident .
  1812.    Call         = Ident '(' Actuals ')' .
  1813.    If           = IF Expr THEN Then: Stats ELSE Else: Stats 'END' .
  1814.    While        = WHILE Expr DO Stats 'END' .
  1815.    Read         = READ '(' Adr ')' .
  1816.    Write        = WRITE '(' Expr ')' .
  1817. > .
  1818. Actuals         = <
  1819.    Expr1        = Expr .
  1820.    Expr2        = Actuals ',' Expr .
  1821. > .
  1822. Expr            = <
  1823.    Less         = Lop: Expr '<' Rop: Expr .
  1824.    Plus         = Lop: Expr '+' Rop: Expr .
  1825.    Times        = Lop: Expr '*' Rop: Expr .
  1826.    Not          = NOT Expr .
  1827.    '()'         = '(' Expr ')' .
  1828.    IConst       = IntegerConst .
  1829.    RConst       = RealConst .
  1830.    False        = FALSE .
  1831.    True         = TRUE .
  1832.    Adr          = <
  1833.       Name      = Ident .
  1834.       Index     = Adr '[' Expr ']' .
  1835.    > .
  1836. > .
  1837.  
  1838.                                                 /* terminals (with attributes)  */
  1839.  
  1840. Ident           : [Ident: tIdent] { Ident       := NoIdent      ; } .
  1841. IntegerConst    : [Integer      ] { Integer     := 0            ; } .
  1842. RealConst       : [Real : REAL  ] { Real        := 0.0          ; } .
  1843.  
  1844. MODULE Tree
  1845.                                 /* external functions for tree construction     */
  1846. PARSER GLOBAL   {
  1847.  
  1848. FROM Tree       IMPORT
  1849.    tTree        , TreeRoot      , ReverseTree   , mMiniLax      , mNoDecl       ,
  1850.    mDecl        , mProc         , mVar          , mNoFormal     , mFormal       ,
  1851.    mType        , mInteger      , mReal         , mBoolean      , mArray        ,
  1852.    mRef         , mNoStat       , mStat         , mAssign       , mCall         ,
  1853.    mIf          , mWhile        , mRead         , mWrite        , mNoActual     ,
  1854.    mActual      , mExpr         , mBinary       , mUnary        , mIntConst     ,
  1855.    mRealConst   , mBoolConst    , mAdr          , mIndex        , mIdent        ,
  1856.    Plus         , Times         , Less          , Not           , NoTree        ;
  1857.  
  1858. VAR nInteger, nReal, nBoolean   : tTree;
  1859. }
  1860.  
  1861. BEGIN   {
  1862.    nInteger     := mInteger     ();
  1863.    nReal        := mReal        ();
  1864.    nBoolean     := mBoolean     ();
  1865. }
  1866.                                 /* attributes for tree construction             */
  1867. DECLARE
  1868.   Decls Decl Formals Formal Type Stats Stat Actuals Expr = [Tree: tTree] .
  1869.  
  1870. RULE                            /* tree construction =                          */
  1871.                                 /* mapping: concrete syntax -> abstract syntax  */
  1872.  
  1873. Prog    = { => {TreeRoot := mMiniLax (mProc (mNoDecl (), Ident:Ident,
  1874.                 Ident:Position, mNoFormal (), ReverseTree (Decls:Tree),
  1875.                 ReverseTree (Stats:Tree)));};                                   } .
  1876. Decls1  = { Tree := {Decl:Tree^.\\Decl.Next := mNoDecl (); Tree := Decl:Tree;};  } .
  1877. Decls2  = { Tree := {Decl:Tree^.\\Decl.Next := Decls:Tree; Tree := Decl:Tree;};  } .
  1878. Var     = { Tree := mVar (NoTree, Ident:Ident, Ident:Position, mRef (Type:Tree));}.
  1879. Proc0   = { Tree := mProc (NoTree, Ident:Ident, Ident:Position, mNoFormal (),
  1880.                     ReverseTree (Decls:Tree), ReverseTree (Stats:Tree));        } .
  1881. Proc    = { Tree := mProc (NoTree, Ident:Ident, Ident:Position, ReverseTree
  1882.            (Formals:Tree), ReverseTree (Decls:Tree), ReverseTree (Stats:Tree)); } .
  1883. Formals1= { Tree := {Formal:Tree^.\\Formal.Next := mNoFormal ();
  1884.                     Tree := Formal:Tree;};                                      } .
  1885. Formals2= { Tree := {Formal:Tree^.\\Formal.Next := Formals:Tree;
  1886.                     Tree := Formal:Tree;};                                      } .
  1887. Value   = { Tree := mFormal (NoTree, Ident:Ident, Ident:Position,
  1888.                     mRef (Type:Tree));                                          } .
  1889. Ref     = { Tree := mFormal (NoTree, Ident:Ident, Ident:Position,
  1890.                     mRef (mRef (Type:Tree)));                                   } .
  1891. Int     = { Tree := nInteger;                                                   } .
  1892. Real    = { Tree := nReal;                                                      } .
  1893. Bool    = { Tree := nBoolean;                                                   } .
  1894. Array   = { Tree := mArray (Type:Tree, Lwb:Integer, Upb:Integer, Lwb:Position); } .
  1895. Stats1  = { Tree := {Stat:Tree^.\\Stat.Next := mNoStat (); Tree := Stat:Tree;};  } .
  1896. Stats2  = { Tree := {Stat:Tree^.\\Stat.Next := Stats:Tree; Tree := Stat:Tree;};  } .
  1897. Assign  = { Tree := mAssign (NoTree, Adr:Tree, Expr:Tree, ':=':Position);       } .
  1898. Call0   = { Tree := mCall (NoTree, mNoActual (Ident:Position), Ident:Ident,
  1899.                     Ident:Position);                                            } .
  1900. Call    = { Tree := mCall (NoTree, ReverseTree (Actuals:Tree), Ident:Ident,
  1901.                     Ident:Position);                                            } .
  1902. If      = { Tree := mIf (NoTree, Expr:Tree, ReverseTree (Then:Tree),
  1903.                     ReverseTree (Else:Tree));                                   } .
  1904. While   = { Tree := mWhile (NoTree, Expr:Tree, ReverseTree (Stats:Tree));       } .
  1905. Read    = { Tree := mRead (NoTree, Adr:Tree);                                   } .
  1906. Write   = { Tree := mWrite (NoTree, Expr:Tree);                                 } .
  1907. Expr1   = { Tree := mActual (mNoActual (Expr:Tree^.\\Expr.Pos), Expr:Tree);      } .
  1908. Expr2   = { Tree := mActual (Actuals:Tree, Expr:Tree);                          } .
  1909. Less    = { Tree := mBinary ('<':Position, Lop:Tree, Rop:Tree, Less);           } .
  1910. Plus    = { Tree := mBinary ('+':Position, Lop:Tree, Rop:Tree, Plus);           } .
  1911. Times   = { Tree := mBinary ('*':Position, Lop:Tree, Rop:Tree, Times);          } .
  1912. Not     = { Tree := mUnary (NOT:Position, Expr:Tree, Not);                      } .
  1913. IConst  = { Tree := mIntConst (IntegerConst:Position, IntegerConst:Integer);    } .
  1914. RConst  = { Tree := mRealConst (RealConst:Position, RealConst:Real);            } .
  1915. False   = { Tree := mBoolConst (FALSE:Position, \\FALSE);                        } .
  1916. True    = { Tree := mBoolConst (TRUE:Position, \\TRUE);                          } .
  1917. Name    = { Tree := mIdent (Ident:Position, Ident:Ident);                       } . 
  1918. Index   = { Tree := mIndex ('[':Position, Adr:Tree, Expr:Tree);                 } .
  1919.  
  1920. END Tree
  1921. .FT "minilax.cg"
  1922. MODULE AbstractSyntax /* ------------------------------------------ */
  1923.  
  1924. TREE IMPORT  {
  1925. FROM Idents     IMPORT tIdent;
  1926. FROM Positions  IMPORT tPosition;
  1927. }
  1928. GLOBAL  {
  1929. FROM Idents     IMPORT tIdent;
  1930. FROM Positions  IMPORT tPosition;
  1931. }
  1932. EVAL Semantics
  1933.  
  1934. PROPERTY INPUT
  1935.  
  1936. RULE
  1937.  
  1938. MiniLAX         = Proc .
  1939. Decls           = <
  1940.    NoDecl       = .
  1941.    Decl         = Next: Decls REV [Ident: tIdent] [Pos: tPosition] <
  1942.       Var       = Type .
  1943.       Proc      = Formals Decls Stats .
  1944.    >.
  1945. >.
  1946. Formals         = <
  1947.    NoFormal     = .
  1948.    Formal       = Next: Formals REV [Ident: tIdent] [Pos: tPosition] Type .
  1949. >.
  1950. Type            = <
  1951.    Integer      = .
  1952.    Real         = .
  1953.    Boolean      = .
  1954.    Array        = Type OUT            [Lwb] [Upb] [Pos: tPosition] .
  1955.    Ref          = Type OUT .
  1956.    NoType       = .
  1957.    ErrorType    = .
  1958. >.
  1959. Stats           = <
  1960.    NoStat       = .
  1961.    Stat         = Next: Stats REV <
  1962.       Assign    = Adr Expr            [Pos: tPosition] .
  1963.       Call      = Actuals             [Ident: tIdent] [Pos: tPosition] .
  1964.       If        = Expr Then: Stats Else: Stats .
  1965.       While     = Expr Stats .
  1966.       Read      = Adr .
  1967.       Write     = Expr .
  1968.    >.
  1969. >.
  1970. Actuals         = <
  1971.    NoActual     =                     [Pos: tPosition OUT] .
  1972.    Actual       = Next: Actuals REV Expr .
  1973. >.
  1974. Expr            =                     [Pos: tPosition] <
  1975.    Binary       = Lop: Expr Rop: Expr [Operator: SHORTCARD] .
  1976.    Unary        = Expr                [Operator: SHORTCARD] .
  1977.    IntConst     =                     [Value            OUT] .
  1978.    RealConst    =                     [Value: REAL      OUT] .
  1979.    BoolConst    =                     [Value: BOOLEAN   OUT] .
  1980.    Adr          = <
  1981.       Index     = Adr Expr .
  1982.       Ident     =                     [Ident: tIdent] .
  1983.    >.
  1984. >.
  1985. Coercions       = <
  1986.    NoCoercion   = .
  1987.    Coercion     = Next: Coercions OUT <
  1988.       Content   = .             /* fetch contents of location    */
  1989.       IntToReal = .             /* convert integer value to real */
  1990.    >.
  1991. >.
  1992.  
  1993. END AbstractSyntax
  1994.  
  1995. MODULE Output /* -------------------------------------------------- */
  1996.  
  1997. PROPERTY OUTPUT
  1998.  
  1999. DECLARE
  2000.    Formals Decls        = [Decls: tObjects THREAD] .
  2001.    Call Ident           = [Object: tObjects] [level: SHORTINT] .
  2002.    If While             = [Label1] [Label2] .
  2003.    Read Write Binary    = [TypeCode: SHORTCARD] .
  2004.    Expr                 = Type Co: Coercions .
  2005.    Index                = type: Type .
  2006.  
  2007. END Output
  2008.  
  2009. MODULE Decls /* -------------------------------------------------- */
  2010.  
  2011. EVAL GLOBAL { FROM Definitions IMPORT mNoObject, mProc, mVar, mProc2, mVar2, Identify; }
  2012.  
  2013. DECLARE Formal Decl     = [Object: tvoid OUT] .
  2014.  
  2015. RULE
  2016.  
  2017. MiniLAX = { Proc:       DeclsIn := nNoObject                            ; } .
  2018. Decl    = { Next:       DeclsIn := nNoObject                            ;
  2019.                         DeclsOut:= Next:        DeclsOut                ;
  2020.                         Object  := {}                                   ; } .
  2021. Proc    = { Next:       DeclsIn := mProc (DeclsIn, Ident, Formals)      ;
  2022.                         Object  := {mProc2 (Next:DeclsIn, Level, CodeSizeIn,
  2023.                                    Formals:DataSizeOut, Decls:DataSizeOut);};
  2024.             Formals:    DeclsIn := nNoObject                            ; } .
  2025. Var     = { Next:       DeclsIn := mVar (DeclsIn, Ident, Type)          ;
  2026.                         Object  := {mVar2 (Next:DeclsIn, Level, DataSizeIn);}; } .
  2027. Formal  = { Next:       DeclsIn := mVar (DeclsIn, Ident, Type)          ;
  2028.                         Object  := {mVar2 (Next:DeclsIn, Level, DataSizeIn);}; } .
  2029. Call    = {             Object  := Identify (Ident, Env)                ; } .
  2030. Ident   = {             Object  := Identify (Ident, Env)                ; } .
  2031.  
  2032. END Decls
  2033.  
  2034. MODULE Formals /* -------------------------------------------------- */
  2035.  
  2036. EVAL GLOBAL     {
  2037. FROM Definitions IMPORT tObjects, GetFormals;
  2038. FROM Tree       IMPORT Formal;
  2039. FROM Types      IMPORT CheckParams;
  2040. }
  2041.  
  2042. DECLARE Actuals = [Formals: MyTree] .
  2043.  
  2044. RULE
  2045.  
  2046. Call    = { Actuals:    Formals := GetFormals (Object)                  ;
  2047.             => { CheckParams (Actuals, Actuals:Formals); }              ; } .
  2048. Actual  = { Next:       Formals := {IF Formals^.Kind = Formal
  2049.                                     THEN Next:Formals := Formals^.Formal.\\Next
  2050.                                     ELSE Next:Formals := Formals;
  2051.                                     END;}                               ; } .
  2052.  
  2053. END Formals
  2054.  
  2055. MODULE Env /* -------------------------------------------------- */
  2056.  
  2057. EVAL GLOBAL     { FROM Definitions      IMPORT tEnv, NoEnv, mEnv; }
  2058.  
  2059. DECLARE Decls Stats Actuals Expr = [Env: tEnv INH] .
  2060.  
  2061. RULE
  2062.  
  2063. MiniLAX = { Proc:       Env     := NoEnv                                ; } .
  2064. Proc    = { Stats:      Env     := mEnv (Decls:DeclsOut, Env)           ;
  2065.             Decls:      Env     := Stats:       Env                     ; } .
  2066.  
  2067. END Env
  2068.  
  2069. MODULE Type /* -------------------------------------------------- */
  2070.  
  2071. EVAL GLOBAL     {
  2072. FROM Definitions IMPORT GetType;
  2073. FROM Types      IMPORT GetElementType, Reduce, ResultType;
  2074. FROM Tree       IMPORT tTree, mBoolean, mInteger, mReal, mRef, mNoType, mNoCoercion;
  2075. }
  2076.  
  2077. RULE
  2078.  
  2079. Expr    = {             Type    := nNoType                              ; } .
  2080. Binary  = {             Type    := ResultType (Lop:Type, Rop:Type, Operator); } .
  2081. Unary   = {             Type    := ResultType (Expr:Type, nNoType, Operator); } .
  2082. IntConst  = {           Type    := nInteger                             ; } .
  2083. RealConst = {           Type    := nReal                                ; } .
  2084. BoolConst = {           Type    := nBoolean                             ; } .
  2085. Adr     = {             Type    := nNoType                              ; } .
  2086. Index   = {             Type    := mRef (GetElementType (type))         ;
  2087.                         type    := Reduce (Adr:Type)                    ; } .
  2088. Ident   = {             Type    := GetType (Object)                     ; } .
  2089.  
  2090. END Type
  2091.  
  2092. MODULE TypeCode /* -------------------------------------------------- */
  2093.  
  2094. EVAL GLOBAL     { FROM ICodeInter IMPORT IntType, RealType, BoolType; }
  2095.  
  2096. DECLARE Read Write Binary = [type: tTree] .
  2097.  
  2098. Read    = {             type     := Reduce (Adr:Type)                   ;
  2099.                         TypeCode := ICodeType [type^.Kind]              ; } .
  2100. Write   = {             type     := Reduce (Expr:Type)                  ;
  2101.                         TypeCode := ICodeType [type^.Kind]              ; } .
  2102. Binary  = {             type     := Reduce (Rop:Type)                   ;
  2103.                         TypeCode := ICodeType [type^.Kind]              ; } .
  2104.  
  2105. END TypeCode
  2106.  
  2107. MODULE Co /* -------------------------------------------------- */
  2108.  
  2109. EVAL GLOBAL     { FROM Types    IMPORT Reduce1, ReduceToRef, Coerce; }
  2110.  
  2111. RULE
  2112.  
  2113. Assign  = { Adr :       Co := Coerce (Adr :Type, ReduceToRef (Adr:Type));
  2114.             Expr:       Co := Coerce (Expr:Type, Reduce (Adr:Type))     ; } .
  2115. If      = { Expr:       Co := Coerce (Expr:Type, Reduce (Expr:Type))    ; } .
  2116. While   = { Expr:       Co := Coerce (Expr:Type, Reduce (Expr:Type))    ; } .
  2117. Read    = { Adr :       Co := Coerce (Adr :Type, ReduceToRef (Adr:Type)); } .
  2118. Write   = { Expr:       Co := Coerce (Expr:Type, Reduce (Expr:Type))    ; } .
  2119. Actual  = { Expr:       Co := {
  2120.                IF Formals^.Kind = NoFormal
  2121.                THEN Expr:Co := mNoCoercion ();
  2122.                ELSE Expr:Co := Coerce (Expr:Type, Reduce1 (Formals^.Formal.Type));
  2123.                END; }                                                   ; } .
  2124. Binary  = { Lop :       Co := Coerce (Lop :Type, Reduce (Lop:Type))     ;
  2125.             Rop :       Co := Coerce (Rop :Type, Reduce (Rop:Type))     ; } .
  2126. Unary   = { Expr:       Co := Coerce (Expr:Type, Reduce (Expr:Type))    ; } .
  2127. Index   = { Adr :       Co := Coerce (Adr :Type, ReduceToRef (Adr:Type));
  2128.             Expr:       Co := Coerce (Expr:Type, Reduce (Expr:Type))    ; } .
  2129.  
  2130. END Co
  2131.  
  2132. MODULE DataSize /* -------------------------------------------------- */
  2133.  
  2134. EVAL GLOBAL     { FROM Types    IMPORT TypeSize; }
  2135.  
  2136. DECLARE Decls Formals = [DataSize THREAD] .
  2137.  
  2138. RULE
  2139.  
  2140. MiniLAX = { Proc:       DataSizeIn      := 0                            ; } .
  2141. Decl    = {             DataSizeOut     := Next:        DataSizeOut     ; } .
  2142. Proc    = { Formals:    DataSizeIn      := 3                            ; } .
  2143. Var     = { Next:       DataSizeIn      :=              DataSizeIn + TypeSize (Reduce1 (Type)); } .
  2144. Formal  = { Next:       DataSizeIn      :=              DataSizeIn + 1  ; } .
  2145.  
  2146. END DataSize
  2147.  
  2148. MODULE CodeSize /* -------------------------------------------------- */
  2149.  
  2150. DECLARE Decls Stats Actuals Expr = [CodeSize THREAD] .
  2151.         Expr Coercions           = [CoercionSize SYN] .
  2152.  
  2153. RUL
  2154.  
  2155. MiniLAX = { Proc: CodeSizeIn  := 0                   ; } .
  2156. Decl    = {       CodeSizeOut := Next: CodeSizeOut   ; } .
  2157. Proc    = { Stats:CodeSizeIn  :=       CodeSizeIn +1 ;                  /* ENT */
  2158.             Decls:CodeSizeIn  := Stats:CodeSizeOut+1 ;                  /* RET */
  2159.             Next: CodeSizeIn  := Decls:CodeSizeOut   ; } .
  2160. Stat    = {       CodeSizeOut := Next: CodeSizeOut   ; } .
  2161. Assign  = { Adr:  CodeSizeIn  :=       CodeSizeIn    ;
  2162.             Expr: CodeSizeIn  := Adr:  CodeSizeOut+Adr:CoercionSize;
  2163.             Next: CodeSizeIn  := Expr: CodeSizeOut+Expr:CoercionSize+1; /* STI */ } .
  2164. Call    = { Actuals:CodeSizeIn:=       CodeSizeIn+1  ;                  /* MST */
  2165.             Next: CodeSizeIn  := Actuals:CodeSizeOut+1;                 /* JSR */ } .
  2166. If      = { Expr: CodeSizeIn  :=       CodeSizeIn    ;
  2167.             Then: CodeSizeIn  := Expr: CodeSizeOut+Expr:CoercionSize+1; /* FJP */
  2168.             Else: CodeSizeIn  := Then: CodeSizeOut+1 ;                  /* JMP */
  2169.             Next: CodeSizeIn  := Else: CodeSizeOut   ; } .
  2170. While   = { Stats:CodeSizeIn  :=       CodeSizeIn +1 ;                  /* JMP */
  2171.             Expr: CodeSizeIn  := Stats:CodeSizeOut   ;
  2172.             Next: CodeSizeIn  := Expr: CodeSizeOut+Expr:CoercionSize+2;
  2173.                                                                    /* INV, FJP */ } .
  2174. Read    = { Adr:  CodeSizeIn  :=       CodeSizeIn    ;
  2175.             Next: CodeSizeIn  := Adr:  CodeSizeOut+Adr:CoercionSize+2;
  2176.                                                                    /* REA, STI */ } .
  2177. Write   = { Expr: CodeSizeIn  :=       CodeSizeIn    ;
  2178.             Next: CodeSizeIn  := Expr: CodeSizeOut+Expr:CoercionSize+1; /* WRI */ } .
  2179. Actual  = { Expr: CodeSizeIn  :=       CodeSizeIn    ;
  2180.             Next: CodeSizeIn  := Expr: CodeSizeOut+Expr:CoercionSize;
  2181.                   CodeSizeOut := Next: CodeSizeOut   ; } .
  2182. Binary  = { Rop:  CodeSizeIn  := Lop:  CodeSizeOut+Lop:CoercionSize;
  2183.                   CodeSizeOut := Rop:  CodeSizeOut+Rop:CoercionSize+1;
  2184.                                                        /* INV, MUL, ADD or LES */ } .
  2185. Unary   = {       CodeSizeOut := Expr: CodeSizeOut+Expr:CoercionSize+1; /* NOT */ } .
  2186. IntConst  = {     CodeSizeOut :=       CodeSizeIn+1  ;                  /* LDC */ } .
  2187. RealConst = {     CodeSizeOut :=       CodeSizeIn+1  ;                  /* LDC */ } .
  2188. BoolConst = {     CodeSizeOut :=       CodeSizeIn+1  ;                  /* LDC */ } .
  2189. Index     = { Expr:CodeSizeIn := Adr:  CodeSizeOut+Adr:CoercionSize;
  2190.                   CodeSizeOut := Expr: CodeSizeOut+Expr:CoercionSize+4;
  2191.                                                          /* CHK, LDC, SUB, IXA */ } .
  2192. Ident     = {     CodeSizeOut :=       CodeSizeIn+1  ;                  /* LDA */ } .
  2193.  
  2194. Expr      = {     CoercionSize:= Co:   CoercionSize  ; } .
  2195. Coercions = {     CoercionSize:= 0                   ; } .
  2196. Content   = {     CoercionSize:= Next: CoercionSize+1;                  /* LDI */ } .
  2197. IntToReal = {     CoercionSize:= Next: CoercionSize+1;                  /* FLT */ } .
  2198.  
  2199. END CodeSize
  2200.  
  2201. MODULE Level /* -------------------------------------------------- */
  2202.  
  2203. DECLARE Decls Formals Stats Actuals Expr = [Level: SHORTINT INH] .
  2204.  
  2205. RULE
  2206.  
  2207. MiniLAX = { Proc:       Level   := 0                                    ; } .
  2208. Proc    = { Formals:    Level   :=              Level + 1               ;
  2209.             Decls:      Level   := Formals:     Level                   ;
  2210.             Stats:      Level   := Formals:     Level                   ; } .
  2211. Call    = {             level   :=              Level                   ; } .
  2212. Ident   = {             level   :=              Level                   ; } .
  2213.  
  2214. END Level
  2215.  
  2216. MODULE Label /* -------------------------------------------------- */
  2217.  
  2218. RULE
  2219.  
  2220. If      = {             Label1  := Else:        CodeSizeIn              ;
  2221.                         Label2  := Else:        CodeSizeOut             ; } .
  2222. While   = {             Label1  := Stats:       CodeSizeIn              ;
  2223.                         Label2  := Expr:        CodeSizeIn              ; } .
  2224.  
  2225. END Label
  2226.  
  2227. MODULE Conditions /* -------------------------------------------------- */
  2228.  
  2229. EVAL GLOBAL     {
  2230. FROM Definitions IMPORT IsDeclared, IsObjectKind, NoObject, Proc, Var;
  2231. FROM Tree       IMPORT Integer, Boolean, Array, ErrorType, NoFormal, IsType, Error;
  2232. FROM Types      IMPORT IsAssignmentCompatible, IsSimpleType;
  2233. }
  2234.  
  2235. RULE
  2236.  
  2237. Decl    = { CHECK NOT IsDeclared (Ident, DeclsIn)
  2238.                ==> Error ("identifier already declared"         , Pos)          ; } .
  2239. Formal  = { CHECK NOT IsDeclared (Ident, DeclsIn)
  2240.                ==> Error ("identifier already declared"         , Pos)          ;
  2241.             CHECK IsSimpleType (Reduce1 (Type))
  2242.                ==> Error ("value parameter must have simple type", Pos)         ; } .
  2243. Array   = { CHECK Lwb <= Upb
  2244.                ==> Error ("lower bound exceeds upper bound"     , Pos)          ; } .
  2245. Assign  = { CHECK IsAssignmentCompatible (Adr:Type, Expr:Type)
  2246.                ==> Error ("types not assignment compatible"     , Pos)          ; } .
  2247. Call    = { CHECK Object^.Kind # NoObject
  2248.                ==> Error ("identifier not declared"             , Pos)          ;
  2249.             CHECK IsObjectKind (Object, Proc)
  2250.                ==> Error ("only procedures can be called"       , Pos)          ; } .
  2251. If      = { CHECK IsType (Reduce (Expr:Type), Boolean)
  2252.                ==> Error ("boolean expression required"         , Expr:Pos)     ; } .
  2253. While   = { CHECK IsType (Reduce (Expr:Type), Boolean)
  2254.                ==> Error ("boolean expression required"         , Expr:Pos)     ; } .
  2255. Read    = { CHECK IsSimpleType (Reduce (Adr:Type))
  2256.                ==> Error ("simple type operand required"        , Adr:Pos)      ; } .
  2257. Write   = { CHECK IsSimpleType (Reduce (Expr:Type))
  2258.                ==> Error ("simple type operand required"        , Expr:Pos)     ; } .
  2259. Binary  = { CHECK Type^.Kind # ErrorType
  2260.                ==> Error ("operand types incompatible"          , Pos)          ; } .
  2261. Unary   = { CHECK Type^.Kind # ErrorType
  2262.                ==> Error ("operand types incompatible"          , Pos)          ; } .
  2263. Index   = { CHECK IsType (Reduce (Adr:Type), Array)
  2264.                ==> Error ("only arrays can be indexed"          , Adr:Pos)      ;
  2265.             CHECK IsType (Reduce (Expr:Type), Integer)
  2266.                ==> Error ("integer expression required"         , Expr:Pos)     ; } .
  2267. Ident   = { CHECK Object^.Kind # NoObject
  2268.                ==> Error ("identifier not declared"             , Pos)          ;
  2269.             CHECK IsObjectKind (Object, Var)
  2270.                ==> Error ("variable required"                   , Pos)          ; } .
  2271.  
  2272. END Conditions
  2273.  
  2274. MODULE TypeDecls /* -------------------------------------------------- */
  2275.  
  2276. TREE IMPORT     {
  2277. FROM SYSTEM     IMPORT ADDRESS;
  2278. FROM Definitions IMPORT tObjects, tEnv;
  2279.  
  2280. PROCEDURE Error (Text: ARRAY OF CHAR; Position: tPosition);
  2281.  
  2282. TYPE tvoid      = RECORD END;
  2283.  
  2284. CONST
  2285.    Plus         = 1;
  2286.    Times        = 2;
  2287.    Less         = 3;
  2288.    Not          = 4;
  2289. }
  2290.  
  2291. EXPORT          { TYPE MyTree = tTree; }
  2292.  
  2293. GLOBAL          {
  2294. FROM Strings    IMPORT tString, ArrayToString;
  2295. IMPORT Errors;
  2296.  
  2297. ROCEDURE Error (Text: ARRAY OF CHAR; Position: tPosition);
  2298.    BEGIN
  2299.       Errors.Message (Text, Errors.Error, Position);
  2300.    END Error;
  2301. }
  2302.  
  2303. EVAL GLOBAL     {
  2304. TYPE MyTree     = Tree.tTree;
  2305.  
  2306. VAR nNoObject   : tObjects;
  2307. VAR nInteger, nReal, nBoolean, nNoType  : tTree;
  2308. VAR ICodeType   : ARRAY [Integer .. Boolean] OF [IntType .. BoolType];
  2309. }
  2310.  
  2311. BEGIN   {
  2312.    nNoObject    := mNoObject    ();
  2313.    nInteger     := mInteger     ();
  2314.    nReal        := mReal        ();
  2315.    nBoolean     := mBoolean     ();
  2316.    nNoType      := mNoType      ();
  2317.  
  2318.    ICodeType [Tree.Integer      ] := IntType    ;
  2319.    ICodeType [Tree.Real         ] := RealType   ;
  2320.    ICodeType [Tree.Boolean      ] := BoolType   ;
  2321. }
  2322.  
  2323. END TypeDecls
  2324. .FT "Definitions.cg"
  2325. TREE Definitions
  2326.  
  2327. IMPORT  {
  2328.    FROM Idents  IMPORT tIdent;
  2329.    FROM SYSTEM  IMPORT ADDRESS;
  2330. }
  2331.  
  2332. EXPORT  {
  2333. CONST NoEnv     = NoDefinitions;
  2334.  
  2335. TYPE
  2336.    tObjects     = tDefinitions; (* type to represent sets of objects    *)
  2337.    tEnv         = tDefinitions; (* type to represent environments       *)
  2338.  
  2339. PROCEDURE Identify      (Ident: tIdent; Env: tEnv): tObjects;
  2340.                         (* return the object associated with 'Ident' in *)
  2341.                         (* the environment 'Env'                        *)
  2342.  
  2343. PROCEDURE IsDeclared    (Ident: tIdent; Objects: tObjects): BOOLEAN;
  2344.                         (* check whether an object having the name      *)
  2345.                         (* 'Ident' is element of the set of objects     *)
  2346.                         (* 'Objects'                                    *)
  2347.  
  2348. PROCEDURE mProc2        (Object: tObjects; Level, Label, ParSize, DataSize: INTEGER);
  2349.                         (* extend the description 'Object' of a         *)
  2350.                         (* procedure by the 4 given attributes          *)
  2351.  
  2352. PROCEDURE mVar2         (Object: tObjects; Level, Offset: INTEGER);
  2353.                         (* extend the description 'Object' of a         *)
  2354.                         (* variable by the 2 given attributes           *)
  2355.  
  2356. PROCEDURE IsObjectKind  (Object: tObjects; Kind: SHORTCARD): BOOLEAN;
  2357.                         (* returns TRUE if the kind of the 'Object'     *)
  2358.                         (* is equal to parameter 'Kind'                 *)
  2359.  
  2360. PROCEDURE GetFormals    (Object: tObjects): ADDRESS;
  2361.                         (* returns the list of formal parameters        *)
  2362.                         (* from the description 'Object' of a procedure *)
  2363.  
  2364. PROCEDURE GetType       (Object: tObjects): ADDRESS;
  2365.                         (* returns the type of the description 'Object' *)
  2366.                         (* of a variable                                *)
  2367. }
  2368.  
  2369. GLOBAL  {
  2370.  
  2371. FROM Idents     IMPORT tIdent;
  2372. FROM SYSTEM     IMPORT ADDRESS;
  2373. FROM Tree       IMPORT mNoType, mNoFormal;
  2374.  
  2375. VAR nNoObject   : tObjects;
  2376.  
  2377. PROCEDURE IsDeclared    (Ident: tIdent; Objects: tObjects): BOOLEAN;
  2378.    BEGIN
  2379.       WHILE Objects^.Kind # NoObject DO
  2380.          IF Objects^.Object.Ident = Ident THEN
  2381.             RETURN TRUE;
  2382.          END;
  2383.          Objects := Objects^.Object.Next;
  2384.       END;
  2385.       RETURN FALSE;
  2386.    END IsDeclared;
  2387.  
  2388. PROCEDURE Identify      (Ident: tIdent; Env: tEnv): tObjects;
  2389.    VAR Objects  : tObjects;
  2390.    BEGIN
  2391.       WHILE Env # NoEnv DO
  2392.          Objects := Env^.Env.Objects;
  2393.          WHILE Objects^.Kind # NoObject DO
  2394.             IF Objects^.Object.Ident = Ident THEN
  2395.                RETURN Objects;
  2396.             END;
  2397.             Objects := Objects^.Object.Next;
  2398.          END;
  2399.          Env := Env^.Env.Hidden;
  2400.       END;
  2401.       RETURN nNoObject;
  2402.    END Identify;
  2403.  
  2404. PROCEDURE mProc2        (Object: tObjects; Level, Label, ParSize, DataSize: INTEGER);
  2405.    BEGIN
  2406.       Object^.Proc.Level        := Level;
  2407.       Object^.Proc.Label        := Label;
  2408.       Object^.Proc.ParSize      := ParSize;
  2409.       Object^.Proc.DataSize     := DataSize;
  2410.    END mProc2;
  2411.  
  2412. PROCEDURE mVar2         (Object: tObjects; Level, Offset: INTEGER);
  2413.    BEGIN
  2414.       Object^.Var.Level         := Level;
  2415.       Object^.Var.Offset        := Offset;
  2416.    END mVar2;
  2417.  
  2418. PROCEDURE IsObjectKind  (Object: tObjects; Kind: SHORTCARD): BOOLEAN;
  2419.    BEGIN
  2420.       RETURN (Object^.Kind = Kind) OR (Object^.Kind = NoObject);
  2421.    END IsObjectKind;
  2422.  
  2423. PROCEDURE GetFormals    (Object: tObjects): ADDRESS;
  2424.    BEGIN
  2425.       IF Object^.Kind = Proc THEN
  2426.          RETURN Object^.Proc.Formals;
  2427.       ELSE
  2428.          RETURN mNoFormal ();
  2429.       END;
  2430.    END GetFormals;
  2431.  
  2432. PROCEDURE GetType       (Object: tObjects): ADDRESS;
  2433.    BEGIN
  2434.       IF Object^.Kind = Var THEN
  2435.          RETURN Object^.Var.Type;
  2436.       ELSE
  2437.          RETURN mNoType ();
  2438.       END;
  2439.    END GetType;
  2440. }
  2441.  
  2442. BEGIN   { nNoObject := mNoObject (); }
  2443.  
  2444. RULE
  2445.  
  2446. Env             = Objects Hidden: Env .
  2447. Objects         = <
  2448.    NoObject     = .
  2449.    Object       = Next: Objects [Ident: tIdent] <
  2450.       Proc      = [Formals: ADDRESS] -> [Level: SHORTINT] [Label] [ParSize] [DataSize] .
  2451.       Var       = [Type: ADDRESS] -> [Level: SHORTINT] [Offset] .
  2452.    > .
  2453. > .
  2454. .FT "Types.puma"
  2455. TRAFO Types PUBLIC
  2456.  
  2457. Reduce                  /* return type without any ref levels           */
  2458.  
  2459. ReduceToRef             /* return type with ref level 1                 */
  2460.  
  2461. Reduce1                 /* return type with 1 ref level removed         */
  2462.  
  2463. RefLevel                /* return number of ref levels of a type        */
  2464.  
  2465. IsSimpleType            /* check whether a type is simple               */
  2466.  
  2467. IsCompatible            /* check whether two types are compatible       */
  2468.  
  2469. IsAssignmentCompatible  /* check whether two types are                  */
  2470.                         /* assignment compatible                        */
  2471.  
  2472. ResultType              /* return the type of the result of             */
  2473.                         /* applying an operator to two operands         */
  2474.  
  2475. CheckParams             /* check a formal list of parameters            */
  2476.                         /* against an actual list of parameters         */
  2477.  
  2478. GetElementType          /* return the type of the elements of           */
  2479.                         /* an array type                                */
  2480.  
  2481. TypeSize                /* return the number of bytes used for          */
  2482.                         /* the internal representation of an            */
  2483.                         /* object of a certain type                     */
  2484.  
  2485. Coerce                  /* returns the coercion necessary to convert    */
  2486.                         /* an object of type 't1' to type 't2'          */
  2487.  
  2488. EXTERN Error
  2489.  
  2490. GLOBAL {
  2491.  
  2492. FROM Positions  IMPORT tPosition;
  2493. FROM Tree       IMPORT
  2494.    tTree        , Array         , Ref           , NoType        ,
  2495.    Plus         , Times         , Less          , Not           ,
  2496.    mBoolean     , mNoType       , mNoCoercion   , Error         ;
  2497.  
  2498. VAR nBoolean, nNoType, nNoCoercion      : tTree;
  2499. }
  2500.  
  2501. BEGIN {
  2502.    nBoolean     := mBoolean     ();
  2503.    nNoType      := mNoType      ();
  2504.    nNoCoercion  := mNoCoercion  ();
  2505. }
  2506.  
  2507. FUNCTION Reduce (Type) Type
  2508.    Ref (t)      RETURN Reduce (t) ?.
  2509.    t            RETURN t ?.
  2510.  
  2511. FUNCTION ReduceToRef (Type) Type
  2512.    Ref (t:Ref)  RETURN ReduceToRef (t) ?.
  2513.    t:Ref        RETURN t ?.
  2514.    t            RETURN t ?.
  2515.  
  2516. FUNCTION Reduce1 (Type) Type
  2517.    Ref (t)      RETURN t ?.
  2518.    t            RETURN t ?.
  2519.  
  2520. FUNCTION RefLevel (Type) INTEGER
  2521.    Ref (t)      RETURN RefLevel (t) + 1 ?.
  2522.    _            RETURN 0 ?.
  2523.  
  2524. PREDICATE IsSimpleType (Type)
  2525.    Array        ? FAIL; .
  2526.    _            ?.
  2527.  
  2528. PREDICATE IsCompatible (Type, Type)
  2529.    Integer      , Integer       ?.
  2530.    Real         , Real          ?.
  2531.    Boolean      , Boolean       ?.
  2532.    Array (t1, Lwb, Upb, _), Array (t2, Lwb, Upb, _) ;
  2533.    Ref (t1)     , t2            ;
  2534.    t1           , Ref (t2)      ? IsCompatible (t1, t2); .
  2535.    NoType       , _             ?.
  2536.    _            , NoType        ?.
  2537.    ErrorType    , _             ?.
  2538.    _            , ErrorType     ?.
  2539.  
  2540. PREDICATE IsAssignmentCompatible (Type, Type)
  2541.    Integer      , Integer       ?.
  2542.    Real         , Real          ?.
  2543.    Real         , Integer       ?.
  2544.    Boolean      , Boolean       ?.
  2545.    Ref (t1)     , t2            ;
  2546.    t1           , Ref (t2)      ? IsAssignmentCompatible (t1, t2); .
  2547.    NoType       , _             ?.
  2548.    _            , NoType        ?.
  2549.    ErrorType    , _             ?.
  2550.    _            , ErrorType     ?.
  2551.  
  2552. FUNCTION ResultType (Type, Type, INTEGER) Type  EXTERN Plus Times Less Not nBoolean;
  2553.    t:Integer    , Integer       , { Plus }      RETURN t        ?.
  2554.    t:Real       , Real          , { Plus }      RETURN t        ?.
  2555.    t:Integer    , Integer       , { Times }     RETURN t        ?.
  2556.    t:Real       , Real          , { Times }     RETURN t        ?.
  2557.    Integer      , Integer       , { Less }      RETURN nBoolean ?.
  2558.    Real         , Real          , { Less }      RETURN nBoolean ?.
  2559.    t:Boolean    , Boolean       , { Less }      RETURN t        ?.
  2560.    t:Boolean    , _             , { Not }       RETURN t        ?.
  2561.    Ref (t1)     , t2            , o             ;
  2562.    t1           , Ref (t2)      , o             RETURN ResultType (t1, t2, o) ?.
  2563.    t:NoType     , _             , _             RETURN t        ?.
  2564.    _            , t:NoType      , _             RETURN t        ?.
  2565.    ErrorType    , _             , _             RETURN NoType   ?.
  2566.    _            , ErrorType     , _             RETURN NoType   ?.
  2567.    ..                                           RETURN ErrorType?.
  2568.  
  2569. PROCEDURE CheckParams (Actuals, Formals)
  2570.    NoActual     , NoFormal      ?.
  2571.    NoActual (Pos), _            ?
  2572.       Error ("too few actual parameters"        , Pos); .
  2573.    Actual (_, Expr (Pos, ..)), NoFormal ?
  2574.       Error ("too many actual parameters"       , Pos); .
  2575.  
  2576. /* alternative 1 */
  2577.  
  2578.    Actual (NextA, Expr (Pos, TypeA, ..)), Formal (_, _, NextF, _, _, TypeF) ?
  2579.       {
  2580.          IF NOT IsCompatible (TypeA, TypeF) THEN
  2581.             Error ("parameter type incompatible", Pos);
  2582.          END;
  2583.          IF NOT (RefLevel (TypeF) - 1 <= RefLevel (TypeA)) THEN
  2584.             Error ("variable required"          , Pos);
  2585.          END;
  2586.       };
  2587.       CheckParams (NextA, NextF); .
  2588.  
  2589. /* alternative 2 */
  2590.  
  2591.    Actual (NextA, Expr (Pos, TypeA, ..)), Formal (_, _, NextF, _, _, TypeF) ?
  2592.       NOT IsCompatible (TypeA, TypeF);
  2593.       Error ("parameter type incompatible"      , Pos);
  2594.       REJECT; .
  2595.  
  2596.    Actual (NextA, Expr (Pos, TypeA, ..)), Formal (_, _, NextF, _, _, TypeF) ?
  2597.       NOT (RefLevel (TypeF) - 1 <= RefLevel (TypeA));
  2598.       Error ("variable required"                , Pos);
  2599.       REJECT; .
  2600.  
  2601.    Actual (NextA, Expr (Pos, TypeA, ..)), Formal (_, _, NextF, _, _, TypeF) ?
  2602.       CheckParams (NextA, NextF); .
  2603.  
  2604. /* alternative 3 */
  2605.  
  2606.    Actual (NextA, Expr (Pos, TypeA, ..)), Formal (_, _, NextF, _, _, TypeF) ?
  2607.       CheckCompatible (Pos, TypeA, TypeF);
  2608.       CheckRefLevel (Pos, TypeA, TypeF);
  2609.       CheckParams (NextA, NextF); .
  2610.  
  2611. PROCEDURE CheckCompatible (tPosition, Type, Type)
  2612.    _    , t1    , t2    ? IsCompatible (t1, t2); .
  2613.    Pos  , ..            ? Error ("parameter type incompatible"  , Pos); .
  2614.  
  2615. PROCEDURE CheckRefLevel (tPosition, Type, Type)
  2616.    _    , t1    , t2    ? RefLevel (t2) - 1 <= RefLevel (t1); .
  2617.    Pos  , ..            ? Error ("variable required"            , Pos); .
  2618.  
  2619. FUNCTION GetElementType (Type) Type
  2620.    Array (t, ..)        RETURN t ?.
  2621.    _                    RETURN NoType ?.
  2622.  
  2623. FUNCTION TypeSize (Type) INTEGER
  2624.    Array (t, Lwb, Upb, _)       RETURN (Upb - Lwb + 1) * TypeSize (t) ?.
  2625.    _                            RETURN 1 ?.
  2626.  
  2627. FUNCTION Coerce (t1: Type, t2: Type) Coercions  EXTERN nNoCoercion;
  2628.    Ref (T1)     , Ref (T2)      RETURN Coerce (T1, T2) ?.
  2629.    Integer      , Real          RETURN IntToReal (nNoCoercion) ?.
  2630.    Ref (T1)     , T2            RETURN Content (Coerce (T1, T2)) ?.
  2631.    ..                           RETURN nNoCoercion ?.
  2632. .FT "ICode.puma"
  2633. TRAFO ICode TREE Tree Definitions PUBLIC Code
  2634.  
  2635. EXTERN
  2636.    ADD BoolType CHK ENT Emit EmitReal FJP FLT FalseCode INV IXA IntType JMP JSR
  2637.    LDA LDC LDI LES MST MUL REA RET RealType STI SUB TrueCode TypeSize WRI
  2638.  
  2639. GLOBAL {
  2640. FROM Tree       IMPORT tTree, Times, Plus, Less;
  2641. FROM Definitions IMPORT tObjects;
  2642. FROM Types      IMPORT TypeSize;
  2643.  
  2644. FROM ICodeInter IMPORT
  2645.    IntType      , RealType      , BoolType      , OpCode        ,
  2646.    Emit         , EmitReal      , TrueCode      , FalseCode     ;
  2647. }
  2648.  
  2649. PROCEDURE Code (t: Tree)
  2650.  
  2651. MiniLax (Proc) ?
  2652.         Code (Proc);
  2653.         .
  2654. Proc (Next := Next:Decls (Definitions.Proc (ParSize := ParSize,
  2655.                 DataSize := DataSize), ..), Decls := Decls, Stats := Stats) ?
  2656.         Emit (ENT, DataSize - ParSize, 0);
  2657.         Code (Stats);
  2658.         Emit (RET, 0, 0);
  2659.         Code (Decls);
  2660.         Code (Next);
  2661.         .
  2662. Var (Next := Next) ?
  2663.         Code (Next);
  2664.         .
  2665. Assign (Next, Adr, Expr, _) ?
  2666.         Code (Adr); Code (Adr::Co);
  2667.         Code (Expr); Code (Expr::Co);
  2668.         Emit (STI, 0, 0);
  2669.         Code (Next);
  2670.         .
  2671. Call (Next, Actuals, _, _, Definitions.Proc (Level := Level, Label := Label,
  2672.                 ParSize := ParSize), level) ?
  2673.         Emit (MST, level - Level, 0);
  2674.         Code (Actuals);
  2675.         Emit (JSR, ParSize - 3, Label);
  2676.         Code (Next);
  2677.         .
  2678. If (Next, Expr, Then, Else, Label1, Label2) ?
  2679.         Code (Expr); Code (Expr::Co);
  2680.         Emit (FJP, Label1, 0);
  2681.         Code (Then);
  2682.         Emit (JMP, Label2, 0);
  2683.         Code (Else);
  2684.         Code (Next);
  2685.         .
  2686. While (Next, Expr, Stats, Label1, Label2) ?
  2687.         Emit (JMP, Label2, 0);
  2688.         Code (Stats);
  2689.         Code (Expr); Code (Expr::Co);
  2690.         Emit (INV, 0, 0);
  2691.         Emit (FJP, Label1, 0);
  2692.         Code (Next);
  2693.         .
  2694. Read (Next, Adr, TypeCode) ?
  2695.         Code (Adr); Code (Adr::Co);
  2696.         Emit (REA, TypeCode, 0);
  2697.         Emit (STI, 0, 0);
  2698.         Code (Next);
  2699.         .
  2700. Write (Next, Expr, TypeCode) ?
  2701.         Code (Expr); Code (Expr::Co);
  2702.         Emit (WRI, TypeCode, 0);
  2703.         Code (Next);
  2704.         .
  2705. Actual (Next, Expr) ?
  2706.         Code (Expr); Code (Expr::Co);
  2707.         Code (Next);
  2708.         .
  2709. Binary (_, _, _, Lop, Rop, {Times}, TypeCode) ?
  2710.         Code (Lop); Code (Lop::Co);
  2711.         Code (Rop); Code (Rop::Co);
  2712.         Emit (MUL, TypeCode, 0);
  2713.         .
  2714. Binary (_, _, _, Lop, Rop, {Plus}, TypeCode) ?
  2715.         Code (Lop); Code (Lop::Co);
  2716.         Code (Rop); Code (Rop::Co);
  2717.         Emit (ADD, TypeCode, 0);
  2718.         .
  2719. Binary (_, _, _, Lop, Rop, {Less}, TypeCode) ?
  2720.         Code (Lop); Code (Lop::Co);
  2721.         Code (Rop); Code (Rop::Co);
  2722.         Emit (LES, TypeCode, 0);
  2723.         .
  2724. Unary (Expr := Expr) ?
  2725.         Code (Expr); Code (Expr::Co);
  2726.         Emit (INV, 0, 0);
  2727.         .
  2728. IntConst (Value := Value) ?
  2729.         Emit (LDC, IntType, Value);
  2730.         .
  2731. RealConst (Value := Value) ?
  2732.         EmitReal (LDC, RealType, Value);
  2733.         .
  2734. BoolConst (Value := {TRUE}) ?
  2735.         Emit (LDC, BoolType, TrueCode);
  2736.         .
  2737. BoolConst (Value := {FALSE}) ?
  2738.         Emit (LDC, BoolType, FalseCode);
  2739.         .
  2740. Index (_, _, _, Adr, Expr, Array (Type, Lwb, Upb, _)) ?
  2741.         Code (Adr); Code (Adr::Co);
  2742.         Code (Expr); Code (Expr::Co);
  2743.         Emit (CHK, Lwb, Upb);
  2744.         Emit (LDC, IntType, Lwb);
  2745.         Emit (SUB, IntType, 0);
  2746.         Emit (IXA, TypeSize (Type), 0);
  2747.         .
  2748. Ident (_, _, _, Ident, Definitions.Var (Level := Level, Offset := Offset), level) ?
  2749.         Emit (LDA, level - Level, Offset);
  2750.         .
  2751. Content (Next) ?
  2752.         Emit (LDI, 0, 0);
  2753.         Code (Next);
  2754.         .
  2755. IntToReal (Next) ?
  2756.         Emit (FLT, 0, 0);
  2757.         Code (Next);
  2758.         .
  2759. .FT "ICodeInter.md"
  2760. DEFINITION MODULE ICodeInter;
  2761.  
  2762. CONST (* coding of OpCode parameters *)
  2763.       IntType   = 1;
  2764.       RealType  = 2;
  2765.       BoolType  = 3;
  2766.       FalseCode = 0;
  2767.       TrueCode  = 1;
  2768.  
  2769.           (* ICode instructions *)
  2770. TYPE OpCode =  (LDA, LDC, LDI, STI, JMP, FJP, ADD, SUB, MUL, INV,
  2771.                 LES, IXA, FLT, WRI, REA, MST, JSR, ENT, RET, CHK);
  2772.  
  2773. PROCEDURE Emit (oc: OpCode; Param1, Param2: CARDINAL);
  2774. PROCEDURE EmitReal (oc: OpCode; Param1: CARDINAL; Param2: REAL);
  2775.   (* repeated calls of 'Emit' and 'EmitReal' write  *)
  2776.   (* the program into 'Code', starting at Code [0]. *)
  2777.  
  2778. PROCEDURE WriteCode; (* 'Code' is written on StdOut *)
  2779. PROCEDURE Interpret; (* executes ICode program *)
  2780.  
  2781. END ICodeInter.
  2782. .FT "ICodeInter.mi"
  2783. IMPLEMENTATION MODULE ICodeInter;
  2784.  
  2785. FROM StdIO IMPORT ReadI, ReadR, WriteCard, WriteI, WriteR, WriteS, WriteNl;
  2786.  
  2787. CONST MaxCode   = 30000;
  2788.       MaxStore  = 10000;
  2789.  
  2790.       SL        = 1; (* static link    *) (* activation record organization *)
  2791.       DL        = 2; (* dynamic link   *)
  2792.       RA        = 3; (* return address *)
  2793.  
  2794. TYPE Ptype  = CARDINAL;    (* type of first parameter *)
  2795.      Qtype  = RECORD
  2796.                 CASE : INTEGER OF
  2797.                 | 1: qc: CARDINAL
  2798.                 | 2: qr: REAL
  2799.                 END
  2800.               END;
  2801.  
  2802.      CodeRange  = [0..MaxCode];         (* type of second parameter *)
  2803.      StoreRange = [0..MaxStore];
  2804.      StoreType  = (Undef, Int, Real, Bool, Adr, Mark);
  2805.  
  2806. VAR Code : ARRAY CodeRange OF RECORD    (* the program *)
  2807.                                  OP : OpCode;
  2808.                                  P  : Ptype;
  2809.                                  Q  : Qtype;
  2810.                               END;
  2811.  
  2812.     Store : ARRAY StoreRange OF RECORD  (* the data *)
  2813.                     CASE Stype: StoreType OF
  2814.                       Int  : Vi : INTEGER
  2815.                     | Real : Vr : REAL
  2816.                     | Bool : Vb : BOOLEAN
  2817.                     | Adr  : Va : StoreRange
  2818.                     | Mark : Vm : CodeRange
  2819.                     END;
  2820.                   END;
  2821.  
  2822.     PC,         (* program address register  *)
  2823.     LastPC      (* highest used code address *)
  2824.           : CodeRange;
  2825.  
  2826.         (* address registers *)
  2827.     AP,   (* points to the beginning of an activation record *)
  2828.     SP    (* points to top of the stack *)
  2829.         : StoreRange;
  2830.  
  2831.     OpCodeText  : ARRAY OpCode OF ARRAY [0..2] OF CHAR;
  2832.  
  2833. PROCEDURE Emit (oc: OpCode; Param1, Param2: CARDINAL);
  2834. BEGIN
  2835.   WITH Code [PC] DO
  2836.     OP   := oc;
  2837.     P    := Param1;
  2838.     Q.qc := Param2
  2839.   END;
  2840.   LastPC := PC;
  2841.   INC (PC);
  2842. END Emit;
  2843.  
  2844. PROCEDURE EmitReal (oc: OpCode; Param1: CARDINAL; Param2: REAL);
  2845. BEGIN
  2846.   WITH Code [PC] DO
  2847.     OP   := oc;
  2848.     P    := Param1;
  2849.     Q.qr := Param2
  2850.   END;
  2851.   LastPC := PC;
  2852.   INC (PC);
  2853. END EmitReal;
  2854.  
  2855. PROCEDURE WriteInstr (Code: OpCode; Param1: Ptype; Param2: Qtype);
  2856. BEGIN
  2857.   WriteS (OpCodeText [Code]);
  2858.   CASE Code OF
  2859.     LDC:                        (* two parameters *)
  2860.       WriteI (Param1, 5);
  2861.       CASE Param1 OF
  2862.         IntType,
  2863.         BoolType: WriteI (Param2.qc, 5);
  2864.       | RealType: WriteR (Param2.qr, 5, 5, 1);
  2865.       END
  2866.  
  2867.   | LDA, JSR, CHK:              (* two parameters *)
  2868.       WriteI (Param1, 5);
  2869.       WriteI (Param2.qc, 5);
  2870.  
  2871.   | MST, ENT, IXA, LES, JMP,
  2872.     FJP, ADD, MUL, REA, WRI:    (* one parameter  *)
  2873.       WriteI (Param1, 5);
  2874.  
  2875.   | LDI, STI, RET, FLT, INV,    (* no parameter   *)
  2876.     SUB:
  2877.   END;
  2878.   WriteNl;
  2879. END WriteInstr;
  2880.  
  2881. PROCEDURE WriteCode;
  2882.   VAR pc : CARDINAL;
  2883. BEGIN
  2884.   WriteNl;
  2885.   WriteS ("Code: (Codelength ="); WriteCard (LastPC+1,4);
  2886.   WriteS (")");
  2887.   WriteNl;
  2888.   IF LastPC # 0 THEN
  2889.     FOR pc := 0 TO LastPC DO
  2890.       WriteI (pc, 5);
  2891.       WriteS (":   ");
  2892.       WITH Code [pc] DO
  2893.         WriteInstr (OP, P, Q)
  2894.       END
  2895.     END
  2896.   END;
  2897.   WriteNl;
  2898. END WriteCode;
  2899.  
  2900. PROCEDURE WriteStore;
  2901.   VAR Sptr : StoreRange;
  2902. BEGIN
  2903.   WriteNl;
  2904.   WriteS ("Store: (Index, Elementtype, Contents)"); WriteNl;
  2905.   
  2906.   FOR Sptr := SP TO 0 BY -1 DO
  2907.     IF AP = Sptr THEN
  2908.       WriteS ("   AP ->"); WriteI (Sptr, 4);
  2909.     ELSE
  2910.       WriteI (Sptr, 12);
  2911.     END;
  2912.     WITH Store [Sptr] DO
  2913.       CASE Stype OF
  2914.       | Int  :  WriteS ("        Int ");
  2915.                 WriteI (Vi, 8);
  2916.       | Real :  WriteS ("        Real");
  2917.                 WriteR (Vr, 8, 8, 1);
  2918.       | Bool :  WriteS ("        Bool");
  2919.                 IF Vb THEN
  2920.                   WriteS ("    TRUE")
  2921.                 ELSE
  2922.                   WriteS ("   FALSE")
  2923.                 END
  2924.       | Adr  :  WriteS ("        Adr ");
  2925.                 WriteI (Va, 8);
  2926.       | Mark :  WriteS ("        Mark");
  2927.                 WriteI (Vm, 8);
  2928.       ELSE WriteS ("    Stype not defined");
  2929.       END;
  2930.       WriteNl;
  2931.     END;
  2932.   END;
  2933.   WriteNl
  2934. END WriteStore;
  2935.  
  2936. PROCEDURE Interpret;
  2937.  
  2938. VAR OP  : OpCode; (* instruction register *)
  2939.     P   : Ptype;
  2940.     Q   : Qtype;
  2941.     sr1, sr2 : StoreRange;
  2942.  
  2943.   PROCEDURE CheckStore (p:CARDINAL);
  2944.   BEGIN
  2945.     IF p > MaxStore THEN WriteS ("Store overflow"); END;
  2946.   END CheckStore;
  2947.     
  2948.   PROCEDURE Base (Ld : CARDINAL): StoreRange;
  2949.       (* walks Ld times back the static link chain *)
  2950.     VAR Sr : StoreRange;
  2951.   BEGIN
  2952.     Sr := AP;
  2953.     WHILE Ld>0 DO
  2954.       Sr := Store [Sr].Vm;
  2955.       DEC (Ld);
  2956.     END;
  2957.     RETURN Sr;
  2958.   END Base;
  2959.  
  2960. BEGIN
  2961.   PC := 0;
  2962.   REPEAT
  2963.     OP := Code [PC].OP;                 (* fetch instruction *)
  2964.     P  := Code [PC].P;
  2965.     Q  := Code [PC].Q;
  2966.  
  2967.     INC(PC);
  2968.  
  2969.     CASE OP OF                          (* execute instruction *)
  2970.  
  2971.        (* load instructions *)
  2972.     | LDA  : INC (SP);
  2973.              Store [SP].Va := Base(P) + Q.qc;
  2974.              Store [SP].Stype := Adr;
  2975.  
  2976.     | LDC  : INC (SP);
  2977.              CASE P OF
  2978.                IntType  : Store [SP].Vi := Q.qc;
  2979.                           Store [SP].Stype := Int;
  2980.              | RealType : Store [SP].Vr := Q.qr;
  2981.                           Store [SP].Stype := Real;
  2982.              | BoolType : Store [SP].Vb := Q.qc = TrueCode;
  2983.                           Store [SP].Stype := Bool;
  2984.              END
  2985.  
  2986.     | LDI  : Store [SP] := Store [Store [SP].Va];
  2987.  
  2988.        (* store instructions *)
  2989.     | STI  : Store [Store [SP-1].Va] := Store [SP];
  2990.              SP := SP-2;
  2991.  
  2992.        (* jump instructions *)
  2993.     | JMP  : PC := P
  2994.  
  2995.     | FJP  : IF NOT Store [SP].Vb THEN
  2996.                PC := P;
  2997.              END;
  2998.              DEC (SP);
  2999.  
  3000.        (* arithmetic instructions *)
  3001.     | ADD  : DEC (SP);
  3002.              CASE P OF
  3003.                IntType  : Store[SP].Vi := Store[SP].Vi + Store[SP+1].Vi;
  3004.              | RealType : Store[SP].Vr := Store[SP].Vr + Store[SP+1].Vr;
  3005.              END
  3006.  
  3007.     | SUB  : DEC (SP);
  3008.              Store[SP].Vi := Store[SP].Vi - Store[SP+1].Vi;
  3009.  
  3010.     | MUL  : DEC (SP);
  3011.              CASE P OF
  3012.                IntType  : Store[SP].Vi := Store[SP].Vi * Store[SP+1].Vi;
  3013.              | RealType : Store[SP].Vr := Store[SP].Vr * Store[SP+1].Vr;
  3014.              END
  3015.  
  3016.        (* logic  instructions *)
  3017.     | INV  : Store[SP].Vb := NOT Store[SP].Vb;
  3018.  
  3019.     | LES  : DEC (SP);
  3020.              CASE P OF
  3021.                IntType  : Store[SP].Vb := Store[SP].Vi < Store[SP+1].Vi;
  3022.              | RealType : Store[SP].Vb := Store[SP].Vr < Store[SP+1].Vr;
  3023.              | BoolType : Store[SP].Vb := Store[SP].Vb < Store[SP+1].Vb;
  3024.              END;
  3025.              Store [SP].Stype := Bool
  3026.  
  3027.        (* address calculating instructions *)
  3028.     | IXA  : DEC (SP);  (* P=number of storage units *)
  3029.              Store [SP].Va := P*Store [SP+1].Va + Store [SP].Va;
  3030.  
  3031.        (* convert instructions *)
  3032.     | FLT  : Store[SP].Vr := FLOAT(CARDINAL(Store[SP].Vi));
  3033.              Store[SP].Stype := Real;
  3034.  
  3035.        (* input-output instructions *)
  3036.     | WRI  : CASE P OF
  3037.                IntType  : WriteI (Store[SP].Vi,5);     WriteNl;
  3038.              | RealType : WriteR (Store[SP].Vr,5,5,1); WriteNl;
  3039.              | BoolType : IF Store [SP].Vb THEN
  3040.                             WriteS ("    1"); WriteNl;
  3041.                           ELSE
  3042.                             WriteS ("    0"); WriteNl;
  3043.                           END
  3044.              END;
  3045.              DEC (SP)
  3046.  
  3047.     | REA  : INC (SP);
  3048.              CASE P OF
  3049.                IntType  : Store[SP].Vi := ReadI();
  3050.                           Store[SP].Stype := Int
  3051.              | RealType : Store[SP].Vr := ReadR();
  3052.                           Store[SP].Stype := Real
  3053.              | BoolType : Store[SP].Vb := ReadI() = 1;
  3054.                           Store[SP].Stype := Bool;
  3055.              END
  3056.  
  3057.        (* subroutine handling instructions *)
  3058.     | MST  :    (* P=(level difference of calling and called procedure)+1 *)
  3059.              Store [SP+SL].Stype := Adr;
  3060.              Store [SP+SL].Va    := Base (P);
  3061.              Store [SP+DL].Stype := Adr;
  3062.              Store [SP+DL].Va    := AP;
  3063.              Store [SP+RA].Stype := Mark;
  3064.                 (* return address is patched in JSR (after  *)
  3065.              SP := SP+3;              (* parameter passing) *)
  3066.  
  3067.     | JSR  : AP := SP-(P+2); (* P=number of locations for parameters *)
  3068.              Store [AP+2].Vm := PC;
  3069.              PC := Q.qc;     (* Q=entry point *)
  3070.  
  3071.     | ENT  : sr2 := SP+P;  (* P=length of local data segment *)
  3072.              FOR sr1 := SP+1 TO sr2 DO
  3073.                Store [sr1].Stype := Undef;
  3074.              END;
  3075.              CheckStore(sr2);
  3076.              SP := sr2;
  3077.  
  3078.     | RET  : SP := AP-1;
  3079.              PC := Store [SP+RA].Vm;
  3080.              AP := Store [SP+DL].Va;
  3081.  
  3082.        (* check instructions *)
  3083.     | CHK  : IF (Store [SP].Vi < INTEGER(P)) OR
  3084.                 (Store [SP].Vi > INTEGER(Q.qc)) THEN
  3085.                 WriteS ("range check error");
  3086.                 WriteNl;
  3087.              END
  3088.  
  3089.     ELSE WriteS ("wrong OpCode :"); WriteS (OpCodeText [OP]); WriteNl;
  3090.     END;
  3091.   UNTIL PC = 0;
  3092. END Interpret;
  3093.  
  3094. BEGIN
  3095.   OpCodeText [LDA] := "LDA";
  3096.   OpCodeText [LDC] := "LDC";
  3097.   OpCodeText [LDI] := "LDI";
  3098.   OpCodeText [STI] := "STI";
  3099.   OpCodeText [JMP] := "JMP";
  3100.   OpCodeText [FJP] := "FJP";
  3101.   OpCodeText [ADD] := "ADD";
  3102.   OpCodeText [SUB] := "SUB";
  3103.   OpCodeText [MUL] := "MUL";
  3104.   OpCodeText [INV] := "INV";
  3105.   OpCodeText [LES] := "LES";
  3106.   OpCodeText [IXA] := "IXA";
  3107.   OpCodeText [FLT] := "FLT";
  3108.   OpCodeText [WRI] := "WRI";
  3109.   OpCodeText [REA] := "REA";
  3110.   OpCodeText [MST] := "MST";
  3111.   OpCodeText [JSR] := "JSR";
  3112.   OpCodeText [ENT] := "ENT";
  3113.   OpCodeText [RET] := "RET";
  3114.   OpCodeText [CHK] := "CHK";
  3115.  
  3116.   Store [0].Stype  := Undef;
  3117.   Store [SL].Stype := Adr;  Store [SL].Va := 0;
  3118.   Store [DL].Stype := Adr;  Store [DL].Va := 0;
  3119.   Store [RA].Stype := Mark; Store [RA].Vm := 0;
  3120.  
  3121.   PC := 0;
  3122.   SP := 3;
  3123.   AP := 1;
  3124. END ICodeInter.
  3125. .FT "minilax.mi"
  3126. MODULE minilax;
  3127.  
  3128. FROM IO         IMPORT CloseIO;
  3129. FROM Parser     IMPORT Parse;
  3130. FROM Tree       IMPORT TreeRoot;
  3131. FROM Semantics  IMPORT BeginSemantics, Eval;
  3132. FROM ICode      IMPORT Code;
  3133. FROM ICodeInter IMPORT Interpret;
  3134.  
  3135. VAR ErrorCount : CARDINAL;
  3136.  
  3137. BEGIN
  3138.    ErrorCount := Parse ();
  3139.    BeginSemantics;
  3140.    Eval (TreeRoot);
  3141.    IF ErrorCount = 0 THEN
  3142.       Code (TreeRoot);
  3143.       Interpret;
  3144.    END;
  3145.    CloseIO;
  3146. END minilax.
  3147. .)l
  3148. .fi
  3149. .sz 12
  3150. .[]
  3151. .[-
  3152. .ds [F Gro87a
  3153. .ds [A J\*(p] Grosch
  3154. .ds [T Reusable Software - A Collection of Modula-Modules
  3155. .ds [I GMD Forschungsstelle an der Universit\\*:at Karlsruhe
  3156. .ds [R Compiler Generation Report No. 4
  3157. .ds [N 4
  3158. .ds [D Sep. 1987
  3159. .][
  3160. .[-
  3161. .ds [F Gro87b
  3162. .ds [A J\*(p] Grosch
  3163. .ds [T Rex - A Scanner Generator
  3164. .ds [I GMD Forschungsstelle an der Universit\\*:at Karlsruhe
  3165. .ds [R Compiler Generation Report No. 5
  3166. .ds [N 5
  3167. .ds [D Dec. 1987
  3168. .][
  3169. .[-
  3170. .ds [F GrV88
  3171. .ds [A J\*(p] Grosch
  3172. .as [A \*(n]B\*(p] Vielsack
  3173. .ds [T The Parser Generators Lalr and Ell
  3174. .ds [I GMD Forschungsstelle an der Universit\\*:at Karlsruhe
  3175. .ds [R Compiler Generation Report No. 8
  3176. .ds [N 8
  3177. .ds [D Apr. 1988
  3178. .][
  3179. .[-
  3180. .ds [F Gro89
  3181. .ds [A J\*(p] Grosch
  3182. .ds [T Ag - An Attribute Evaluator Generator
  3183. .ds [I GMD Forschungsstelle an der Universit\\*:at Karlsruhe
  3184. .ds [R Compiler Generation Report No. 16
  3185. .ds [N 16
  3186. .ds [D Aug. 1989
  3187. .][
  3188. .[-
  3189. .ds [F GrE90
  3190. .ds [A J\*(p] Grosch
  3191. .as [A \*(n]H\*(p] Emmelmann
  3192. .ds [T A Tool Box for Compiler Construction
  3193. .ds [I GMD Forschungsstelle an der Universit\\*:at Karlsruhe
  3194. .ds [R Compiler Generation Report No. 20
  3195. .ds [N 20
  3196. .ds [D Jan. 1990
  3197. .][
  3198. .[-
  3199. .ds [F Gro91a
  3200. .ds [A J\*(p] Grosch
  3201. .ds [T Ast - A Generator for Abstract Syntax Trees
  3202. .ds [I GMD Forschungsstelle an der Universit\\*:at Karlsruhe
  3203. .ds [R Compiler Generation Report No. 15
  3204. .ds [N 15
  3205. .ds [D Sep. 1991
  3206. .][
  3207. .[-
  3208. .ds [F Gro91b
  3209. .ds [A J\*(p] Grosch
  3210. .ds [T Puma - A Generator for the Transformation of Attributed Trees
  3211. .ds [I GMD Forschungsstelle an der Universit\\*:at Karlsruhe
  3212. .ds [R Compiler Generation Report No. 26
  3213. .ds [N 26
  3214. .ds [D July 1991
  3215. .][
  3216. .[-
  3217. .ds [F Gro91c
  3218. .ds [A J\*(p] Grosch
  3219. .ds [T Preprocessors
  3220. .ds [I GMD Forschungsstelle an der Universit\\*:at Karlsruhe
  3221. .ds [R Compiler Generation Report No. 24
  3222. .ds [N 24
  3223. .ds [D Feb. 1991
  3224. .][
  3225. .[-
  3226. .ds [F NAJ76
  3227. .ds [A K\*(p]\*(a]V\*(p] Nori
  3228. .as [A \*(c]U\*(p] Ammann
  3229. .as [A \*(c]K\*(p] Jensen
  3230. .as [A \*(c]H\*(p]\*(a]H\*(p] N\\*:ageli
  3231. .as [A \*(m]C\*(p] Jacobi
  3232. .ds [T The Pascal-P Compiler: Implementation Notes
  3233. .nr [P 0
  3234. .ds [P 53
  3235. .ds [R Bericht 10
  3236. .ds [I Eidgen\\*:ossische Technische Hochschule
  3237. .ds [C Z\\*:urich
  3238. .ds [D July 1976
  3239. .][
  3240. .[-
  3241. .ds [F WaG84
  3242. .ds [A W\*(p]\*(a]M\*(p] Waite
  3243. .as [A \*(n]G\*(p] Goos
  3244. .ds [T Compiler Construction
  3245. .ds [I Springer Verlag
  3246. .ds [C New York, NY
  3247. .ds [D 1984
  3248. .][
  3249. .bp 1
  3250. .lp
  3251. .b Contents
  3252. .sp
  3253. .xp
  3254.